整理一下0-1背包、完全背包、多重背包问题。

背包问题

01背包

概述

01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2至Wn，与之相对应的价值为P1,P2至Pn。（这是最基础的背包问题）

思路

在前n件物品中，选取若干件物品放入所剩空间为w的背包中的所能获得的最大价值。（实际上是对一件件物品选与不选的问题）
我们用f[i][j]表示在前 i 件物品中选择若干件放在已用空间为 j 的背包里所能获得的最大价值
对一个物体，只有两种情况：

  1. 选：f[i][j] = f[i - 1][j - W[i]] + P[i]
  2. 不选：f[i][j] = f[i - 1][j]

由此可以得到状态转移方程：
f[i][j] = max(f[i - 1][j - W[i]] + P[i], f[i - 1][j]);

代码

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
/**
 * @param m 表示背包的容量
 * @param n 表示物品的个数
 * @param w 表示物品所占空间
 * @param p 表示物品的价值
**/
public static int[][] backpack01(int m,int n,int[] w,int[] p){
    //f[i][v]表示前i件物品恰放入一个容量为m的背包可以获得的最大价值
    int[][] f = new int[n + 1][m + 1];
    for(int i = 0; i < n + 1; i++){
    	f[i][0] = 0;
    }
    for(int j = 0; j < m + 1; j++){
    	f[0][j] = 0;
    }

    for(int i = 1; i < n + 1; i++){
        for(int j = 1; j < m + 1; j++){
            if(w[i - 1] <= j){	//物品所占空间小于剩余空间，w[i-1]中i-1是对应数组w中的取值，下面w[i-1]p[i-1]同理
                if(f[i - 1][j] < f[i - 1][j - w[i - 1]] + p[i - 1]){
                    f[i][j] = f[i - 1][j - w[i - 1]] + p[i - 1];
                }else{
                    f[i][j] = f[i - 1][j];
                }
            }else{
                f[i][j] = f[i - 1][j];
            }
        }
    }
    return f;
}

完全背包

概述

完全背包问题跟01背包的区别是01背包每个物品只能选一次，总共就这几个，而完全背包问题是每个物品可以无限选，只要装得下。可以看成是有几种物品，每种都无限多个。

思路

01背包在选第i个物品时，容积够用情况下，只有2种状态可选，放还是不放，找出最大价值的选择
而完全背包在选第i种物品时，容积够用情况下，可能有2种以上状态可选，放1个，或者2个，3个，或者不放。找出最大价值的选择
可以利用k = j/w[i]算出最多可以放几个，然后状态转移方程改为f[i][j] = max(f[i - 1][j - k*w[m]] + k * p[i]) 从0到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
27
28
29
30
31
32
33
34
/**
     * @param m 表示背包的容量
     * @param n 表示物品的个数
     * @param w 表示物品所占空间
     * @param p 表示物品的价值
**/
    //f[i][v]表示前i件物品恰放入一个容量为m的背包可以获得的最大价值
    public static int[][] backpack02(int m,int n,int[] w,int[] p){

        int[][] f = new int[n + 1][m + 1];
        //初始化边界
        for(int i = 0; i < n + 1; i++){
            f[i][0] = 0;
        }
        for(int j = 0; j < m + 1; j++){
            f[0][j] = 0;
        }

        for(int i = 1; i < n + 1; i++){
            for(int j = 1; j < m + 1; j++){
                if(w[i - 1] <= j){
                    int k = j / w[i - 1];
                    for(int t = 0; t < k + 1; t++){
                        if(f[i - 1][j - t * w[i - 1]] + t * p[i - 1] > f[i][j]){
                            f[i][j] = f[i - 1][j - t * w[i - 1]] + t * p[i - 1];
                        }
                    }
                }else{
                    f[i][j] = f[i - 1][j];
                }
            }
        }
        return f;
    }

多重背包

概述

与“完全背包”相比，在每个物品的选取次数上给出了限定，即选取次数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
26
27
28
29
30
31
32
/**
     * @param m 表示背包的容量
     * @param n 表示物品的个数
     * @param w 表示物品所占空间
     * @param p 表示物品的价值
     * @param num 表示物品的数量
**/
    //f[i][v]表示前i件物品恰放入一个容量为m的背包可以获得的最大价值
    public static int[][] backpack03(int m,int n,int[] w,int[] p,int[] num){

        int[][] f = new int[n + 1][m + 1];
        //初始化边界
        for(int i = 0; i < n + 1; i++){
            f[i][0] = 0;
        }
        for(int j = 0; j < m + 1; j++){
            f[0][j] = 0;
        }

        for(int i = 1; i < n + 1; i++) { //遍历每个物品
            for (int j = 1; j < m + 1; j++) {
                for (int k = 0; (k <= num[i - 1]) && (k >= 0); k++) {
                    if (j > k * w[i - 1]) {
                        if (f[i - 1][j - k * w[i - 1]] + k * p[i - 1] > f[i][j]) {
                            f[i][j] = f[i - 1][j - k * w[i - 1]] + k * p[i - 1];
                        }
                    }
                }
            }
        }
        return f;
    }