1. 简介

  1. 0-1背包问题 : 对于物品而言只能选择1个或者0个两种情况(选不选)
  2. 完全背包 : 对于物品而言可以无限制选取,也可以不选
  3. 多重背包 : 对于某物品而言最多能够选择从s个,同样也可不选
  4. 混合背包 : 有些物品可以选择1,有些物品可以选择无数个,有些物品只能选择是s[i]个.即:01背包+完全背包+多重背包
  5. 二维费用背包 : 在重量的基础上增加空间的限制

  6. 分组背包:多重背包的普遍版本 一些物品捆绑在一起,每一组物品中只能选择其中的一个物品s[i]

  7. 贪心 : 对于物品只需要价值比最大,物品可分

1. 0-1背包 参考

dp 解释 : 前i个物品在空间为j的情况下的 (最值)

1.朴素版

普通0-1背包: dp[i][j] = max(dp[i-1][j] , dp[i-1][j−w[i]] + v[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int w = sc.nextInt();
    int n = sc.nextInt();
    int[][] dp = new int[n+1][w+1];
    int[] weight = new int[n+1];
    int[] value = new int[n+1];
    for (int i = 1; i <=n ; i++) {
      weight[i] = sc.nextInt();
      value[i] = sc.nextInt();
    }
    // 若是比第i个物品在j 的空间下放不下 就取前一个物品的最大值 填充 ,若放得下 就比较放于不放 
    for (int i = 1; i <=n ; i++) {
      for (int j = 1; j <=w ; j++) {
        if(weight[i] > j){
          dp[i][j] = dp[i-1][j];
        }else{      //变数在这里 dp递推方程
          int v1 = dp[i-1][j];
          int v2 = dp[i-1][j-weight[i]] + value[i]*weight[i]; 
          dp[i][j] = Math.max(v1,v2);
        }
      }
    }
    System.out.println(dp[n][w]);
  }
}

2.一维空间优化版

空间优化0-1背包: f[j] = max(f[j] , f[j−w[i]] + v[i])

1
2
3
4
for (int i = 1; i <= n; i++)
	for (int j = W; j >= w[i]; j--)
		f[j] = max(f[j], f[j - w[i]] + v[i]);
printf("%d\n", f[W]);

理解空间优化:

我们可以看到内层循环对于容量的计算是逆序的。本来之前二维的数组，是利用上一层来转移到下一层来表示每个物品最多只能拿一次。现在丢弃了一个物品维度，无法这样表示。所以可以倒序枚举空间大小，转移之前的状态都是未更新的，这样来表示每个物品只能够拿一次

当我们计算f[j]时，用到了f[j]和f[j-w[i]]，f[j]表示不拿当前的物品，f[j-w[i]]表示拿当前的物品。因为对于容量是从大到小逆序计算的，所以f[j-w[i]]是没有被更新过的，表示还没有拿当前层的物品，这样就表示每个物品最多只能拿一次。

而如果正向从小到大进行计算，f[j-w[i]]则是已经更新过的，这样就表示每个物品都能拿无数次，这样正向计算就成了完全背包。

2.完全背包 参考

1.朴素版

dp[i][j] = max(dp[i-1][j] , dp[i][j−w[i]] + v[i])

朴素版类似上面 只是dp递推时可以是 max(dp[i-1][j] , dp[i][j−w[i]] + v[i]) 即可以多次选择本物品

2.一维空间优化版

此为洛谷1616题,求单位时间内采药价值最大
(运用一维优化空间)

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

3.多重背包 参考

  • 解法类似01背包 转化为0k背包
    1.朴素版
    dp[i][j] = max(dp[i-1][j-k*w[i]] + k*v[i]) | 0<=k<=n[i]
  • 朴素版类: 在前i个物品可选，容量为j的情况下，选k个物品的最大值
  • 即可以选择k次本物品
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int v = sc.nextInt();
        int[] weight = new int[n+1];
        int[] values = new int[n+1];
        int[] counts = new int[n+1];
        for (int i = 0; i <n ; i++) {
            weight[i] = sc.nextInt();
            values[i] = sc.nextInt();
            counts[i] = sc.nextInt();
        }
        int[] dp = new int[v+1];
        for (int i = 0; i <n ; i++) {
            for (int j = v; j >= 0 ; j--) {
                for (int k = 1; k<=counts[i] && k*weight[i] <= j ; k++) {
                    dp[j] = Math.max(dp[j],dp[j-k*weight[i]]+k*values[i]);
                }
            }
        }
        System.out.println(dp[v]);
    }
}
2.二进制优化
  • 首先将所有k*w 单独表示成一个个重kw价值kv的物品
  • 利用类似快速幂的思想，用k = 1,2,4,8.. + 余数可以表示取k次该物品
  • 时间复杂度从N^3 降到N^2*logN
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int w = sc.nextInt();
        List<Pair<Integer,Integer>> goods = new ArrayList<>();
        for (int i = 0; i <n ; i++) {
            int weight = sc.nextInt();
            int value = sc.nextInt();
            int count = sc.nextInt();
            for (int j = 1; j <=count ; j*=2) {
                count -= j;
                goods.add(new Pair<>(weight*j,value*j));
            }
            if(count > 0) goods.add(new Pair<>(count*weight,count*value));
        }

        int[] dp = new int[w+1];
        for (Pair<Integer,Integer> good:goods) {
            for (int j = w; j >=good.getKey() ; j--) {
                dp[j] = Math.max(dp[j],dp[j-good.getKey()]+good.getValue());
            }
        }
        System.out.println(dp[w]);
    }

4.混合背包 参考

  • 将各种背包分类处理

    1.朴素版

  • 将多重背包处理为01背包

  • 对01和完全背包分开处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class 混合背包 {

    private static class Thing{
        int kind;   // 种类
        int weight;  // 重量
        int value;   // 价值
        Thing(int kind,int weight,int value){
            this.kind = kind;
            this.value = value;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int w = sc.nextInt();
        List<Thing> things = new ArrayList<>();
        for (int i = 0; i <n ; i++) {
            int weight = sc.nextInt();
            int value = sc.nextInt();
            int count = sc.nextInt();
            if(count < 0) things.add(new Thing(-1,weight,value));       // 01背包
            else if(count == 0) things.add(new Thing(0,weight,value));  // 完全背包
            else{                                                            // 多重背包
                for (int j = 1; j <=count ; j*=2) {
                    count -= j;
                    things.add(new Thing(-1,weight*j,value*j));
                }
                if(count > 0) things.add(new Thing(-1,weight*count,value*count));
            }
        }

        int[] dp = new int[w+1];
        for (Thing thing:things) {
            if(thing.kind < 0){
                for (int j = w; j >=thing.weight ; j--) dp[j] = Math.max(dp[j],dp[j-thing.weight]+thing.value);
            }else{
                for (int j = thing.weight; j <= w ; j++) dp[j] = Math.max(dp[j],dp[j-thing.weight]+thing.value);
            }
        }
        System.out.println(dp[w]);
    }
}

5.二维费用背包 参考

  • dp[i] 变为二维的 dp[i][j] 表示二维空间的容量

    1.朴素版

  • 和一维背包类似，只是做二维的扩展了

  • 如本题就是在01背包的基础上做了空间的限制
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;
public class 二维费用背包 {
    // 在重量的基础上 限制体积
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int w = sc.nextInt();   // 重量
        int v = sc.nextInt();   // 体积
        int[][] dp = new int[w+1][v+1];
        for (int i = 0; i <n ; i++) {
            int weight = sc.nextInt();
            int volume = sc.nextInt();
            int value = sc.nextInt();
            for (int j = w; j >=weight ; j--) {
                for (int k = v; k >=volume ; k--) {
                    dp[j][k] = Math.max(dp[j][k],dp[j-weight][k-volume]+value);
                }
            }
        }
        System.out.println(dp[w][v]);
    }
}

6.分组背包 参考

  • 实际上也是基于01背包
  • 是多重背包的普遍版，相当于多重背包的分解为 w…kw的物品 而分组背包就是w[0]..w[k]的物品 同组物品之间无关联
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.Scanner;
public class 分组背包 {
    // 在01背包的基础上 划分组
    // 相当于 多重背包的 普遍情况
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int w = sc.nextInt();
        int[] dp = new int[w+1];
        for (int i = 0; i < n; i++) {
            int len = sc.nextInt();
            int[] weight = new int[len+1];
            int[] values = new int[len+1];
            for (int j = 0; j <len ; j++) {
                weight[j] = sc.nextInt();
                values[j] = sc.nextInt();
            }
            for (int j = w; j >=0 ; j--) {
                for (int k = 0; k < len; k++) {
                    if(j >= weight[k]) dp[j] = Math.max(dp[j],dp[j-weight[k]]+values[k]);
                }
            }
        }
        System.out.println(dp[w]);
    }
}