描述：给定背包的体积，物品的体积和权值，每个物品仅能使用一次，如何放物体使背包的的利益达到最大、 [0-1]背包]是较为简单的动态规划问题，也是其余背包问题的基础。
动态规划是不断决策求最优解的过程，「0-1 背包」即是不断对第 i个物品的做出决策，
[0-1]正好代表不选与选两种决定。
题目：
输入样例
4 5 1 2 2 4 3 4 4 5
输出样例：
8
基本思路：
1.n物品个数，m为背包体积，使用w[i]记录权值，v[i]记录体积，f[i][j]记录选择前i个物体，在不超过j体积下的最优解
最终答案就是f[n][m];
2.f[i][j]的状态依赖于之前的状态；即f[i[][j]依赖于f[i - 1][j]的状态；也可以理解为所有的状态由f[0][j]推得
f[i][j]的状态不好算出来，但是f[0][j]的状态必定为0，由f[0][j]可以算出f[1][j]的,由f[1][j]又可算出f[2][j]的递推可得出全部。f[1][1] f[2][2] f[3][3]他们每个都减去第i个物品的权值最大值仍不变，最后在加上w[i]即可
即( f[1 - 1][j - v[1] ]) + w[i]
题解代码：
import java.util.*; import java.io.*; public class Main{ static int N = 1010; static int n,m; static int[][] f = new int[N][N]; static int[] v = new int[N]; static int[] w = new int[N]; public static void main(String[] args){ Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); //读取n和m的值 for (int i = 1;i <= n;i++ ){ int a = sc.nextInt();int b = sc.nextInt(); v[i] = a;w[i] = b; } for (int i = 1;i <= n;i++)//n层每一层算出选择n个物品且体积不超过j的最优解 for (int j = 1;j <= m;j++){ f[i][j] = f[i - 1][j]; //取前一个值方便比较，和如果放不下第i个物品，那么f[i][j] = f[i - 1][j]; if (j >= v[i]) //把所有能放下i物品的情况与不不能放下的比较,最终结果f[i[m]必然是该状态的最优解 f[i][j] = Math.max(f[i][j],f[i - 1][j - v[i]] + w[i]); //把f[i][j]分为两部分f[i - 1][j]和f[i - 1][j - v[i]] + w[i]; } System.out.println(f[n][m]); } }
优化成一维数组
因为
if (j < v[i]) f[i][j] = f[i - 1][j]; else f[i][j] = Math.max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]);
可以看出f[i][j]只与f[i - 1][j]有关，前面几层都没有意义所以我们可以优化成一维数组
代码：
import java.util.*; import java.io.*; public class Main{ static int N = 1010; static int n,m; static int[] f = new int[N]; static int[] v = new int[N]; static int[] w = new int[N]; public static void main(String[] args){ Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); //读取n和m的值 for (int i = 1;i <= n;i++ ){ int a = sc.nextInt();int b = sc.nextInt(); v[i] = a;w[i] = b; } for (int i = 1;i <= n;i++) for (int j = m;j >= v[i];j--){ f[j] = Math.max(f[j],f[j - v[i]] + w[i]); } System.out.println(f[m]); } }
