2、一维dp

思路：

可以看出f[i][~]只依赖于f[i-1][~]，所以根本没必要保留之前的f[i-2][~]等状态值

• f[j]： N 件物品，背包容量j情况下的最大价值

要获得第i轮的状态，需要正序  小的先更新，大的再更新

import java.util.*;class Main
{static int N=1010;static int[] f=new int[N];public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),m=sc.nextInt();for(int i=1;i<=n;i++){int v=sc.nextInt(),w=sc.nextInt();for(int j=v;j<=m;j++)f[j]=Math.max(f[j],f[j-v]+w);}System.out.print(f[m]);}
}

4. 多重背包问题 I - 每种物品数量有限件，体积至多j，总价值最大

4. 多重背包问题 I - AcWing题库

题目：

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

1、二维dp

思路：

• 设f[i][j]：前i件物品，总体积不超过j的最大总价值
• 答案即f[n][m]

• 选0件第i个物品：f[i][j]=f[i-1][j]
• 选1件第i个物品：f[i][j]=f[i-1][j-v]+w
• 选2件第i个物品：f[i][j]=f[i-1][j-2v]+2w
• ……
• 选s件第i个物品：f[i][j]=f[i-1][j-sv]+sw

import java.util.*;class Main
{static int N=110;static int[] v=new int[N],w=new int[N],s=new int[N];static int[][] f=new int[N][N];public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),m=sc.nextInt();for(int i=1;i<=n;i++) {v[i]=sc.nextInt();w[i]=sc.nextInt();s[i]=sc.nextInt();}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=0;k<=s[i];k++)if(j>=k*v[i]) f[i][j]=Math.max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);//当k=0时，f[i-1][j-v[i]*k]+w[i]*k就是f[i-1][j]System.out.print(f[n][m]);}
}

2、一维dp

思路：

可以看出f[i][~]只依赖于f[i-1][~]，所以根本没必要保留之前的f[i-2][~]等状态值

• f[j]： N 件物品，背包容量j情况下的最大价值

要获得第i-1轮的状态，需要逆序  大的先更新，小的再更新

import java.util.*;class Main
{static int N=110;static int[] f=new int[N];public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),m=sc.nextInt();for(int i=1;i<=n;i++){int v=sc.nextInt(),w=sc.nextInt(),s=sc.nextInt();for(int j=m;j>=1;j--)for(int k=0;k<=s;k++)if(j>=k*v) f[j]=Math.max(f[j],f[j-k*v]+k*w);}System.out.print(f[m]);}
}

2、二进制优化版

5. 多重背包问题 II - AcWing题库 

思路：

• 多重背包无法像完全背包那样用类似“错位相减”的方法优化，因此我们考虑问题转化：
• 水果店里有 40 个苹果，小明计划购买 n   ( 1 ≤ n ≤ 40 )  个苹果，试问如何让小明尽可能快速地完成购买？一个显而易见的暴力做法是，让小明一个个拿（单位是个），但效率过于低下。事实上，店员可事先准备好 6 个箱子，每个箱子中的苹果数量分别为 [1,2,4,8,16,9]，再让小明按箱子拿（单位是箱子），无论小明计划购买多少个，他最多只需要拿 6  次，而在暴力做法中，小明最多需要拿 40 次。

• 在暴力求解多重背包问题时，对于每种物品i，都要从0开始枚举到s[i]，效率低
• 现在对于每种物品i，将这s[i]个物体分到 ⌊ log2s[i] ⌋+1个箱子里
• 相当于转化成每次取一个箱子的量，也就是01背包问题
• 也就是将s[i]拆分成若干个二进制的数的组合
• 原本结果数为NVS=4×10^9
• 优化后为NVlog2S=24000

import java.util.*;class Main
{static int N=250000;static int[] v=new int[N],w=new int[N];static int[] f=new int[N];public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),m=sc.nextInt();int cnt=0;for(int i=1;i<=n;i++) {int vv=sc.nextInt(),ww=sc.nextInt(),s=sc.nextInt();//对每一种物品i进行装箱for(int k=1;k<=s;k*=2){cnt++;v[cnt]=vv*k; w[cnt]=ww*k;s-=k;}if(s>0){cnt++;v[cnt]=vv*s;w[cnt]=ww*s;}}n=cnt;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.print(f[m]);}
}

9. 分组背包问题 - 每组物品最多选1个，体积至多j，总价值最大

9. 分组背包问题 - AcWing题库

题目：

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

1、一维dp

思路：

• 设f[j]：前N件物品，总体积不超过j的最大总价值
• 答案即f[m]

对于二维dp进行分析，三重循环会超时：

• 不选第i组的物品：f[i][j]=f[i][j]
• 选第i组第1个物品：f[i][j]=f[i-1][j-v[i][1]]+w[i][1]
• 选第i组第2个物品：f[i][j]=f[i-1][j-v[i][2]]+w[i][2]
• ……
• 选第i组第s个物品：f[i][j]=f[i-1][j-v[i][s]]+w[i][s]

 

要获得第i-1轮的状态，需要逆序  大的先更新，小的再更新

f[j]=max(f[j],f[j-v[i][k]]+w[i][k])

import java.util.*;class Main
{static int N=110;static int[][] v=new int[N][N];static int[][] w=new int[N][N];static int[] s=new int[N];static int[] f=new int[N];public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),m=sc.nextInt();for(int i=1;i<=n;i++){s[i]=sc.nextInt();for(int j=1;j<=s[i];j++){v[i][j]=sc.nextInt();w[i][j]=sc.nextInt();}}for(int i=1;i<=n;i++)for(int j=m;j>=1;j--)for(int k=1;k<=s[i];k++)if(j>=v[i][k])f[j]=Math.max(f[j],f[j-v[i][k]]+w[i][k]);System.out.print(f[m]);}
}

3382. 整数拆分 - 完全背包dp

3382. 整数拆分 - AcWing题库

题目：

思路：

可以将问题转化成：

有m种物品（2的幂的种数），容量为n的背包，某种物品可以选无限个，问不超过容量n的最大方案数

也就是完全背包问题，定义f[j]为用2的幂凑出的值不超过j的最大方案数，则f[n]即是答案

import java.util.*;class Main
{static int N=1000010,mod=1000000000;static int[] f=new int[N];public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();//定义f[j]用2的幂凑出的值不超过j的最大方案数f[0]=1;for(int i=1;i<=n;i*=2) //枚举2的幂数for(int j=i;j<=n;j++)f[j]=(f[j]+f[j-i])%mod;System.out.print(f[n]);}
}