从01背包问题一维优化到多重背包问题二进制、单调队列优化总结

背包问题很经典，但从来都没有从头到尾总结过。

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

多重背包问题的变动是，每个物品不止可以选择1次了，但要求还是在有限容量下装入最大的价值。

相当于问题除了给出背包容量V，每种物品的价值W，之外，还给了每种物品的可选数量S

多重背包问题的做法有

  • 将多重背包问题拆分为01背包问题，每种物品的每个我都选择一下0或1选与不选，这种做法时间复杂度较高。

    适用数据范围为：

    $0<N,V≤1000$
    $0<v_i,w_i≤1000$ (因为题目一般的可解计算量为$10^7$ )

  • 范围超了有，二进制优化方法

    适用数据范围为：

    $0<N \le 1000$

    $0<V \le 2000$

    $0<v_i,w_i,s_i≤2000$

  • 再大还有单调队列优化方法

    适用数据范围为：

    $0<N \le 1000$

    $0<V \le 20000$

    $0<v_i,w_i,s_i≤20000$

01背包问题

题目：https://www.acwing.com/problem/content/2/

不断对第i个物品做出决策，[0-1] 代表选与不选两种抉择

将状态$f[i][j]$优化到一维$f[j]$，实际上只需要做一个等价变形。

为什么可以这样变形呢？我们定义的状态$f[i][j]$可以求得任意合法的 $i$ 与 $j$ 最优解，但题目只需要求得最终状态$f[n][m]$，因此我们只需要一维的空间来更新状态。

  1. 状态$f[j]$ 定义：N件物品，背包容量 $j$ 下的最优解
  2. 注意枚举背包容量 $j$ 必须从 $V$ 开始
  3. 为什么一维情况下枚举背包容量需要逆序？ 在2维情况下，状态 $f[i][j]$ 是由上一轮 $i-1$ 的状态得来的， $f[i][j]$ 与 $f[i-1][j]$ 是相互独立的。而优化到1维后，如果还是正序遍历，则有 $f[较小体积]$ 更新到 $f[较大体积]$， 则有可能本应该用第 $i-1$ 轮的状态却用的是第 $i$ 轮的状态
  4. 例如，一维状态第$i$ 轮对体积为3的物品进行决策，则$f[7]$ 由 $f[4]$ 更新而来，这里的$f[4]$ 正确应该是 $f[i-1][4]$，但从后小岛大枚举 $j$ 这里的 $f[4]$ 在第 $i$ 轮却成了 $f[i][4]$。 当逆序枚举背包容量 $j$ 时， 我们求$f[7]$ 同样由 $f[4]$ 更新。这里的 $f[4]$ 还没有在第 $i$ 轮计算，所以实际计算的 $f[4]$ 仍是 $f[i-1][4]$
  5. 简单来说，一维情况下正序更新状态 $f[j]$ 需要用到前面计算的状态已经被污染，逆序则不会有这样的问题
  6. 状态转移方程为 $f[j] = max(f[j], f[j-v[i]]+ w[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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class Main{
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        
        int[] v=new int[N+1];
        int[] w=new int[N+1];
        
        for(int i=1;i<=N;i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        
         //dp1(v,w, N, V);// 无优化数组
      	 dp2(v,w, N, V);// 优化为1维数组
    }
    
    public static void dp1(int[] v,int [] w, int N, int V){
        int[][] dp = new int[N+1][V+1];
        dp[0][0]= 0;
        for(int i=1;i<=N;i++){
            for(int j=1;j<=V;j++){
                if(j<v[i]) dp[i][j]=dp[i-1][j];
                else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-v[i]]+w[i]);
                }
            }
        }
        System.out.println(dp[N][V]);
    }
  
    public static void dp2(int[] v,int [] w, int N, int V){
          int[] dp = new int[V+1];
          dp[0]= 0;
          for(int i=1;i<=N;i++){
              for(int j=V;j>=v[i];j--){
                  // if(j<v[i]) dp[j]=dp[j];
                  // else{
                  dp[j] = Math.max(dp[j], dp[j-v[i]]+w[i]);
                  // }
              }
          }
          System.out.println(dp[V]);
      }

}

还可以优化输入

处理数据时，我们是一个物品一个物品，一个体积一个体积的去枚举

因此可以不必开两个数组去记录体积和价值，而是边输入边处理。

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

多重背包问题1

题目：https://www.acwing.com/problem/content/4/

多重背包问题，在给出每个物品的体积V和价值W的基础上，让每个物品不只可选1次

完全背包和01背包的区别是完全背包中每个物品可以用无限次，而多重背包不是无限次用。

最直接也最耗时的思路是，所有的可选的物品种类和次数都询问一次选或不选，也就是当成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
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int V = scanner.nextInt();

        int[] f = new int[110];

        for (int i = 0; i < N; i++) {
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            int s = scanner.nextInt();
            for (int j = V; j >= 0; j--) {
                for (int k = 1; k <= s && k * v <= j; k++) {
                    f[j] = Math.max(f[j], f[j - k * v] + k * w);
                }
            }
        }

        System.out.println(f[V]);
    }
}

多重背包问题2

题目：https://www.acwing.com/problem/content/5/

这道题和多重背包问题1其实是一样的，只不过数量级有变化，要求你用二进制优化的方法来解。

那么什么是二进制优化法？

上一道题是将每种物品拆成单份的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
 即 v,w,s = v,w,7 时：
 正常拆分：-> (v,w)，(v,w)，(v,w)，(v,w)，(v,w)，(v,w)，(v,w)
 二进制拆分：-> (v,w),(v<<1,w<<1),(v<<2,w<<2)

 7 : 1 ,2, 4
 0
 1
 2
 3 = 1+2
 4
 5= 1+4
 6 =2+4
 7=1+2+4
 <p>
 s - 1 -2 - 4 - 8  ....
 减 2的幂  减到不能减为止 用s - (1+2+4+8...)
 就可以把物品分成log(s)份 而不是s份
 <p>
 log(2000)=11
 1000*11*2000 = 2*10^7
 所以将每个物品拆成log份
 
 模拟
1 2 4 8 16 32 64 128 256 512 1024
这十一个数可以拼凑出0-2047间的所有整数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16................
1 2 1+2 4 4+1 4+2 4+2+1 8 8+1 8+2 8+2+1 8+4 8+4+1 8+4+2 8+4+2+1 16................
所以在使用二进制将si个i物品拆包组装成一个个大包之后我们总归可以通过01背包的枚举方式来得到一个正确的i物品选用数量，比如说应该选67件i物品，那么体现成我们选取了 价值为64w的物品一件 + 价值为2w的物品一件 + 价值为1*w的物品一件

为什么这么拆有用？

上一题的状态转移方程是

我们首先确认三点：

（1）我们知道转化成01背包的基本思路就是：判断每件物品我是取了你好呢还是不取你好。

（2）我们知道任意一个实数可以由二进制数来表示，也就是$2^0 - 2^k$其中一项或几项的和。

（3）这里多重背包问的就是每件物品取多少件可以获得最大价值。

如果仍然不是很能理解的话，取这样一个例子:要求在一堆苹果选出n个苹果。我们传统的思维是一个一个地去选，选够n个苹果就停止。这样选择的次数就是n次

二进制优化思维就是：现在给出一堆苹果和10个箱子，选出n个苹果。将这一堆苹果分别按照1,2,4,8,16,…..512分到10个箱子里，那么由于任何一个数字x ∈[1,1024]
都可以从这10个箱子里的苹果数量表示出来，但是这样选择的次数就是 ≤10次 。

这样利用二进制优化，时间复杂度就从$O(n^3)降到O(n^2logS)$,从$410^9$降到了$210^7$。

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.Scanner;

public class Main{
   	Scanner scanner = new Scanner(System.in);
    
    void run1(){
        int N = scanner.nextInt();
        int V = scanner.nextInt();
        
        int[] v_arr = new int[12010];
        int[] w_arr = new int[12010];
        
        int cnt = 0; // 分组的组别
        for(int i=1;i<=N;i++){
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            int s = scanner.nextInt();
            int k =1; //组别里的类别个数
            while(k<=s){
                cnt++; //组别先增加
                v_arr[cnt] = v*k; //整体体积
                w_arr[cnt] = w*k; //整体价值
                s-=k;   
                k*=2;
            }
            //剩余一组
            if(s>0){
                cnt++;
                v_arr[cnt]= v*s;
                w_arr[cnt]= w*s;
            }
        }
        
        int[] f = new int[V+1];
        N = cnt;
        // 01背包
        for(int i=1;i<=N;i++){
            for(int j=V;j>=v_arr[i];j--){
                f[j] = Math.max(f[j] , f[j-v_arr[i]]+w_arr[i]);
            }
        }
        System.out.println(f[V]);
    }

    public static void main(String[] args) {
        new Main().run1();
    }
}

多重背包问题3

题目：https://www.acwing.com/problem/content/description/6/

$0<N \le 1000$

$0<V \le 20000$

$0<v_i,w_i,s_i≤20000$

如果还以上面的二进制优化来做，复杂度为 $1000 log(20000) 20000 = 3*10^8$ 会超时。

1
2
3
for(int i=1;i<=N;i++)  //第一重循环
        for(int j=0;j<=V;j++)  //第二重循环
            for (int k = 0; k <= s[i] && k * v[i] <= j; k ++ )  //第三重循环

考虑到对于每次层 $i，j$ 只与 j % v+kv 有关，k 的范围 $[0,s]$

优化二三重循环,将每一层 j 按 j%v 分成v组，节省了第二重循环中 $ j+v…j+kv$ 的时间，将两重循环优化为遍历一次 m；

$f[i][j]=max(f[i][j],f[i-1][j-kv[i]]+k*w[i]) $相当于求每一组在s个范围内的最大值，单调队列O（1）时间即可；

时间复杂度应该是O(NV)

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
import java.util.Scanner;

public class Main{
   	Scanner scanner = new Scanner(System.in);
    
    void run1(){
        int N = scanner.nextInt();
        int V = scanner.nextInt();
        
        int[] v_arr = new int[V+1];
        int[] w_arr = new int[V+1];
        
        int[] f = new int[V+1];
        int[] g = new int[V+1];
        int[] q = new int[V+1];
        
        for(int i=1;i<=N;i++){
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            int s = scanner.nextInt();
            for(int j=0;j<v;j++){
                int hh,tt;
                hh=0,tt=-1;
                for(int k=j;k<=m;k+=vi){
                    g[k] = f[k];//每次f[k]都可能会更新， 预先保存f[i-1, k]的值 
                    if(hh<=tt&&(k-q[hh])/vi>si) hh++;//保证保证不超前si个
                    while(hh<=tt&&g[q[tt]]+(k-q[tt])/vi*wi <f[k]) tt--;//单调队列入队方法
                    q[++tt] = k;
                    f[k] = g[q[hh]]+(k-q[hh])/vi*wi;
                }
            }
        }
        
    }

    public static void main(String[] args) {
        new Main().run1();
    }
}