动态规划:背包问题全

01背包问题

1.题目

有 N件物品和一个容量为 V的背包，每件物品有各自的价值且只能被选择一次，要求在有限的背包容量下，装入的物品总价值最大。

「0-1 背包」是较为简单的动态规划问题，也是其余背包问题的基础。

动态规划是不断决策求最优解的过程，「0-1 背包」即是不断对第 i 个物品的做出决策，「0-1」正好代表不选与选两种决定。

2.题解代码

2.1版本1 二维

（1）状态f[i][j]定义：只从前i个物品选，且选取物品总体积不超过j的最大价值

（2）状态计算（如何求f[i][j]）：将f[i][j]看作集合，划分为不包含第i个物品和包含第i个物品两类，不包含第i个物品为从前i-1个物品选，总体积不超过j所构成的集合，取最大值，即f[i-1][j]，包含第i个物品为从前i-1个物品选，总体积不超过j-vi的集合，取最大值然后加上选取物品i的权重，即f[i-1][j-vi] wi；最后在两者之间选取最大值，即可求得f[i][j]。

（3）考虑背包容量是否大于物品i的体积:

j<v[i]: 无需考虑选取第i个物品的情况，对应代码：f[i][j] = f[i - 1][j]

j>=v[i]：选取和不选取第i个物品都得考虑， 对应代码：Math.max(f[i - 1][j], f[i - 1][j - v[i]] w[i])

代码如下：

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

2.2版本2 一维

将状态f[i][j]优化为以为f[j], 实际上只需要做一个等价变形。

由f[i][j] = Math.max(f[i-1][j], f[i-1][j-v[i]] w[i])我们可知，我们每次求取f[i][j]的时候，都只用到了第i-1层的数据，而且题目只需要求得最总状态f[n][m],中间状态不需要存储。，所以我们每次求第i层的数据时只需要将第i-1层的数据覆盖即可。但是注意小细节，此时在一维情况下枚举背包容量时，需要逆序遍历，因为f[j-v[i]]在f[j]的左边，如果正序遍历的话，我们用到的数据就不是第i-1层的数据了，而是刚更新过的第i层数据。

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

完全背包问题

1.题目

有 N种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

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

输出最大价值。

2.题解代码

2.1简单版

（1）状态f[i][j]定义：只从前i个物品选，且选取物品总体积不超过j的最大价值

（2）状态计算：将集合f[i][j]划分为分别选取0~k个物品i，再对选取物品i的个数进行枚举，限制条件为k * v[i] <= j, 然后求最大值即可。

基本代码如下：

1.  
   import java.util.Scanner;
2.  
    
3.  
   public class Main{
4.  
   public static void main(String[] args){
5.  
   Scanner sc = new Scanner(System.in);
6.  
   int n = sc.nextInt();
7.  
   int m = sc.nextInt();
8.  
   int[] v = new int[n 1];
9.  
   int[] w = new int[n 1];
10.  
    int[][] f = new int[n 1][m 1];
11.  
    for (int i = 1; i <= n; i ) {
12.  
    v[i] = sc.nextInt();
13.  
    w[i] = sc.nextInt();
14.  
    }
15.  
    for (int i = 1; i <= n; i ) {
16.  
    for (int j = 0; j <= m; 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][m]);
23.  
    }
24.  
    }

2.2优化版

优化思路：

f[i , j ] = 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 , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] w , f[i-1,j-3*v] 2*w , .....)

由上两式，可得出如下递推关系：

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

有了上面的关系，那么其实k循环可以不要了，核心代码优化成这样：

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

这个代码和01背包的非优化写法很像啊!!!我们对比一下，下面是01背包的核心代码

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

两个代码其实只有一句不同（注意下标）

f[i][j] = max(f[i][j],f[i-1][j-v[i]] w[i]);//01背包

f[i][j] = max(f[i][j],f[i][j-v[i]] w[i]);//完全背包问题

综上所述，完全背包的最终写法如下：

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

多重背包问题（二进制优化）

1.题目

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

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

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

输出最大价值。

2.解题代码

多重背包问题简单版和完全背包问题简单版是相同的解题思路，这里直接上优化版

在完全背包中,通过两个状态转移方程：

f[i,j]=max(f[i−1,j],f[i−1,j−v] w,f[i−1,j−2v] 2w,f[i−1,j−3v] 3w,.....)

f[i,j−v]=max(f[i−1,j−v],f[i−1,j−2v] w,f[i−1,j−2v] 2w,.....)

通过上述比较，可以得到f[i][j] = max(f[i-1][j],f[i][j-v] w)

再来看下多重背包,

f[i,j] = max(f[i−1,j],f[i−1,j−v] w,f[i−1,j−2v] 2w,.....f[i−1,j−Sv] Sw,)

f[i,j-v] = max(f[i−1,j−v],f[i−1,j−2v] w,.....f[i−1,j−Sv] (S−1)w,f[i−1,j−(S 1)v] Sw)

这里比完全背包方程多了一项，不能像完全背包一样去优化

二进制优化思路：

将每一组拥有的个数进行二进制计算，使每组进行二进制分割之后变为01背包问题，即假设有1023个；二进制的思维，将1023按照1，2，4，8，16，... ，512分到10个箱子里，根据数学知识，如何一个我们需要拿的数字x∈[0,1023]都可以用这10个箱子里的苹果数量表示出来，这样的话时间复杂度从O(n3)降到O(n2logS)

1.  
   import java.util.Scanner;
2.  
    
3.  
   public class Main{
4.  
   static int N = 12010;//逐一枚举最大是N*logS
5.  
    
6.  
   public static void main(String[] args){
7.  
   Scanner sc = new Scanner(System.in);
8.  
   int n = sc.nextInt();
9.  
   int m = sc.nextInt();
10.  
    int[] v = new int[N];
11.  
    int[] w = new int[N];
12.  
    int[] f = new int[m 1];
13.  
    int cnt = 0;
14.  
    for (int i = 1; i <= n; i ) {
15.  
    int a = sc.nextInt();
16.  
    int b = sc.nextInt();
17.  
    int s = sc.nextInt();
18.  
    int k = 1;
19.  
    while(k <= s) {
20.  
    cnt ;
21.  
    v[cnt] = a * k; //整体体积
22.  
    w[cnt] = b * k; // 整体价值
23.  
    s -= k; // s要减小
24.  
    k *= 2; // 组别里的个数增加
25.  
    }
26.  
    if (s > 0) {
27.  
    cnt ;
28.  
    v[cnt] = a * s;
29.  
    w[cnt] = b * s;
30.  
    }
31.  
    }
32.  
    n = cnt;//枚举次数由个数变成组别数
33.  
            //01背包一维优化
34.  
    for (int i = 1; i <= n; i ) {
35.  
    for (int j = m; j >= v[i]; j --) {
36.  
    f[j] = Math.max(f[j], f[j-v[i]] w[i]);
37.  
    }
38.  
    }
39.  
    System.out.println(f[m]);
40.  
    }
41.  
    }

分组背包问题

1. 题目

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

每组物品有若干个，同一组内的物品最多只能选一个。

每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

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

输出最大价值。

2.题解代码

（1）状态f[i][j]定义：只从前i组物品选，且选取物品总体积不超过j的最大价值

（2）状态计算（如何求f[i][j]）：将f[i][j]看作集合，划分为不包含第i组的物品和包含第i组的第k个物品两类，不包含第i组的物品为从前i-1组物品选，总体积不超过j所构成的集合，取最大值，即f[i-1][j]，包含第i组的第k个物品为从前i-1个物品选，总体积不超过j-v[i,k]的集合，取最大值然后加上选取第i组物品的第k个物品的权重，即f[i-1][j-v[i,k]] w[i,k]；最后在两者之间选取最大值，即可求得f[i][j]。

代码如下：

1.  
   import java.util.Scanner;
2.  
    
3.  
   public class Main{
4.  
   static int N = 110;
5.  
   public static void main(String[] args){
6.  
   Scanner sc = new Scanner(System.in);
7.  
   int n = sc.nextInt();
8.  
   int m = sc.nextInt();
9.  
   int[][] v = new int[n 1][N];
10.  
    int[][] w = new int[n 1][N];
11.  
    int[] s = new int[n 1];
12.  
    int[][] f = new int[n 1][m 1];
13.  
    for (int i = 1; i <= n; i ) {
14.  
    s[i] = sc.nextInt();
15.  
    for (int j = 1; j <= s[i]; j ) {
16.  
    v[i][j] = sc.nextInt();
17.  
    w[i][j] = sc.nextInt();
18.  
    }
19.  
    }
20.  
     
21.  
    for (int i = 1; i <= n; i ) {
22.  
    for (int j = 0; j <= m; j ) {
23.  
    f[i][j] = f[i-1][j];
24.  
    for (int k = 0; k <= s[i]; k ) {
25.  
    if (j >= v[i][k]){
26.  
    f[i][j] = Math.max(f[i][j], f[i-1][j-v[i][k]] w[i][k]);
27.  
    }
28.  
    }
29.  
    }
30.  
    }
31.  
    System.out.println(f[n][m]);
32.  
    }
33.  
    }

因为只用到了第i-1列，所以可以仿照01背包的套路逆向枚举体积

1.  
   import java.util.Scanner;
2.  
    
3.  
   public class Main{
4.  
   static int N = 110;
5.  
   public static void main(String[] args){
6.  
   Scanner sc = new Scanner(System.in);
7.  
   int n = sc.nextInt();
8.  
   int m = sc.nextInt();
9.  
   int[][] v = new int[n 1][N];
10.  
    int[][] w = new int[n 1][N];
11.  
    int[] s = new int[n 1];
12.  
    int[] f = new int[m 1];
13.  
    for (int i = 1; i <= n; i ) {
14.  
    s[i] = sc.nextInt();
15.  
    for (int j = 1; j <= s[i]; j ) {
16.  
    v[i][j] = sc.nextInt();
17.  
    w[i][j] = sc.nextInt();
18.  
    }
19.  
    }
20.  
     
21.  
    for (int i = 1; i <= n; i ) {
22.  
    for (int j = m; j >= 0; j --) {
23.  
    for (int k = 1; k <= s[i]; k ) {
24.  
    if (j >= v[i][k]){
25.  
    f[j] = Math.max(f[j], f[j-v[i][k]] w[i][k]);
26.  
    }
27.  
    }
28.  
    }
29.  
    }
30.  
    System.out.println(f[m]);
31.  
    }
32.  
    }