一、思路

f[i, j]与01背包问题一样，也可以看作是只考虑前i个物品，且总体积不大于j的所有选法的集合，完全背包求的结果相当于求这个集合的最大值

二、状态计算

对该问题的状态计算即对这个集合的划分，如图所示
image.png
0表示不选第i个物品 f[i,j]=f[i-1,j]
1表示选1个第i个物品f[i,j]=f[i-1,j-v[i]]+w[i]
2表示选2个第i个物品
…
k表示选k个第i个物品 f[i,j] = f[i-1,j-k*v[i]] + k*w[i]

最左边不选第i个物品的集合可以视为k=0的特殊情况，所以最后可以得到最终表达式为
f[i,j] = f[i-1,j-k*v[i]] + k*w[i]

  1. import java.util.Scanner;
  2. public class Main{
  3.     public static void main(String[] args) {
  4.         Scanner in = new Scanner(System.in);
  5.         int N = in.nextInt();
  6.         int V = in.nextInt();
  7.         int[] v = new int[1005];
  8.         int[] w = new int[1005];
  9.         int[][] f = new int[1005][1005];
  10.         for (int i = 1; i <= N; i++) {
  11.             v[i] = in.nextInt();
  12.             w[i] = in.nextInt();
  13.         }
  15.         for (int i = 1; i <= N; i++) {
  16.             for (int j = 0; j <= V; j++) {
  17.                 for (int k = 0; k * v[i] <= j; k++) {
  18.                     f[i][j] =Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
  19.                 }
  20.             }
  21.         }
  22.         System.out.println(f[N][V]);
  23.     }
  24. }

三、代码优化

  1. for (int k = 0; k * v[i] <= j; k++) {
  2.     f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
  3. }

这段代码其实是取了各个子集的最大值：

  1. // v[i]为v   w[i]为w
  2. f[i][j]=Math.max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2*v]+2*w,f[i-1][j-3*v]+3*w+...+f[i-1][j-k*v]+k*w)
  1. f[i][j-v]=Math.max(f[i-1][j-v],f[i-1][j-2*v]+w,f[i-1][j-3*v]+2*w,f[i-1][j-4*v]+3*w+...+f[i-1][j-k*v]+(k-1)*w)

我们可以发现代码3等价于代码2中的后一部分+w，所以我们可以利用代码3对代码2做一个数学上的优化

  1. f[i][j]=Math.max(f[i-1][j],f[i][j-v]+w)

所以优化重点的三循环部分就可以优化成两循环了

  1. for (int i = 1; i <= N; i++) {
  2.     for (int j = 0; j <= V; j++) {
  3.         f[i][j] = f[i-1][j];
  4.         if(j>=v[i]) f[i][j]=Math.max(f[i-1][j],f[i][j-v[i]]+w[i]);
  5.     }
  6. }

跟01背包同理，直接去掉i的那一维，变成一维

四、最终代码

  1. import java.util.Scanner;
  2. public class Main{
  3.     public static void main(String[] args) {
  4.         Scanner in = new Scanner(System.in);
  5.         int N = in.nextInt();
  6.         int V = in.nextInt();
  7.         int[] v = new int[1005];
  8.         int[] w = new int[1005];
  9.         int[] f = new int[1005];
  10.         for (int i = 1; i <= N; i++) {
  11.             v[i] = in.nextInt();
  12.             w[i] = in.nextInt();
  13.         }
  15.         for (int i = 1; i <= N; i++) {
  16.             for (int j = v[i]; j <= V; j++) {
  17.                 f[j]=Math.max(f[j],f[j-v[i]]+w[i]);
  18.             }
  19.         }
  20.         System.out.println(f[V]);
  21.     }
  22. }

五、与01背包区别

二维代码，更加直观

// 完全背包
f[i][j] = Math.max(f[i-1][j], f[i-1][j-v]+w);
// 01背包
f[i][j] = Math.max(f[i-1][j], f[i][j-v]+w);