动态规划之完全背包

arctic_fox / 2023-07-08 / 原文

1. 题目

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。

2. 完全背包动态规划表

完全背包问题是一种动态规划问题，它的特点是每种物品可以取无限次，而不是只能取一次。

一个例子是：有一个背包的容积为5，有4种物品，每种物品的体积和价值分别为(1, 2), (2, 4), (3, 4), (4, 5)。求在不超过背包容积的情况下，能装入的最大价值是多少？

物品的信息如下：

物品编号	体积	价值
1	1	2
2	2	4
3	3	4
4	4	5

一个可能的动态规划表如下：

i\j	1	2	3	4	5
0	0	0	0	0	0
1	2	4	6	8	10
2	2	4	6	8	10
3	2	4	6	8	10
4	2	4	6	8	10

其中，i表示前i种物品，j表示背包的剩余容量，表格中的值表示最大价值。加粗的部分表示状态转移方程的更新。

状态转移方程可以表示为：

其中，dp[i][j]表示前i种物品装入剩余容量为j的背包的最大价值，v[i]和w[i]分别表示第i种物品的体积和价值。

从表格中可以看出，最终的答案是10，即装入两个体积为1，价值为2的物品和一个体积为3，价值为4的物品。

3. 朴素二维写法

二维写法的三种分别是：

- 一种是在状态转移方程中，用一个循环来枚举每种物品的取法，即k=0,1,2,…,j/v[i]，然后取最大值。这种写法的时间复杂度是O(NMV)，其中N是物品数量，M是背包容量，V是物品体积的最大值。这种写法的优点是比较通用和容易理解，缺点是比较慢。
  - f[i][j]=0≤k≤v[i]j max(f[i−1][j−kv[i]]+kw[i])
- 另一种是在状态转移方程中，利用f[i][j-v[i]]+w[i]和f[i-1][j]的关系，将循环优化为一个max操作。这种写法的时间复杂度是O(NM)，其中N是物品数量，M是背包容量。这种写法的优点是比较快，缺点是比较难想到和证明。
  - f[i][j]=max(f[i−1][j],f[i][j−v[i]]+w[i])
- 还有一种是在状态转移方程中，将f[i][j]和f[i-1][j]的关系用一个max操作表示，然后将j的遍历顺序从逆序改为正序。这种写法的时间复杂度也是O(NM)，其中N是物品数量，M是背包容量。这种写法的优点是比较简洁和巧妙，缺点是比较难理解和记忆。
  - f[i][j]=max(f[i−1][j],f[i−1][j−v[i]]+w[i])

3.1 二维带枚举实现

public class BackpackComplete1 {
    public static int maxValue(int n, int V, int[] v, int[] w) {
        // 动态规划数组
        int[][] dp = new int[n + 1][V + 1];
        // 初始化第一行和第一列为0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= V; j++) {
            dp[0][j] = 0;
        }
        // 状态转移
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j]; // 不装第i种物品
                for (int k = 0; k * v[i - 1] <= j; k++) { // 枚举装k个第i种物品
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * v[i - 1]] + k * w[i - 1]); // 比较不装和装第i种物品的最大价值
                }
            }
        }
        // 返回最大价值
        return dp[n][V];
    }
    
    public static void main(String[] args) {
        // 物品数量
        int n = 4;
        // 背包容量
        int V = 5;
        // 物品体积数组
        int[] v = {1, 2, 3, 4};
        // 物品价值数组
        int[] w = {2, 4, 4, 5};
        
        // 调用方法并输出结果
        System.out.println(maxValue(n, V, v, w));
    }
}

3.2 二维带

public class BackpackComplete2 {
    public static int maxValue(int n, int V, int[] v, int[] w) {
         // 动态规划数组
         int[][] dp = new int[n + 1][V + 1];
         // 初始化第一行和第一列为0
         for (int i = 0; i <= n; i++) {
             dp[i][0] = 0;
         }
         for (int j = 0; j <= V; j++) {
             dp[0][j] = 0;
         }
         // 状态转移
         for (int i = 1; i <= n; i++) {
             for (int j = v[i - 1]; j <= V; j++) { // 只考虑装得下第i种物品的情况
                 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - v[i - 1]] + w[i - 1]); // 比较不装和装第i种物品的最大价值
             }
             for (int j = v[i - 1] - 1; j >= 0; j--) { // 只考虑装不下第i种物品的情况
                 dp[i][j] = dp[i - 1][j]; // 不装第i种物品
             }
         }
         // 返回最大价值
         return dp[n][V];
    }
    
    public static void main(String[] args) {
         // 物品数量
         int n = 4;
         // 背包容量
         int V = 5;
         // 物品体积数组
         int[] v = {1, 2, 3, 4};
         // 物品价值数组
         int[] w = {2, 4, 4, 5};
         
         // 调用方法并输出结果
         System.out.println(maxValue(n, V, v, w));
    }
}

3.3 二维带

public class BackpackComplete3 {
    public static int maxValue(int n, int V, int[] v, int[] w) {
         // 动态规划数组
         int[][] dp = new int[n + 1][V + 1];
         // 初始化第一行和第一列为0
         for (int i = 0; i <= n; i++) {
             dp[i][0] = 0;
         }
         for (int j = 0; j <= V; j++) {
             dp[0][j] = 0;
         }
         // 状态转移
         for (int i = 1; i <= n; i++) {
             for (int j = 1; j <= V; j++) { // 正序遍历容量
                 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i - 1]] + w[i - 1]); // 比较不装和装第i种物品的最大价值
             }
         }
         // 返回最大价值
         return dp[n][V];
    }
    
    public static void main(String[] args) {
         // 物品数量
         int n = 4;
         // 背包容量
         int V = 5;
         // 物品体积数组
         int[] v = {1, 2, 3, 4};
         // 物品价值数组
         int[] w = {2, 4, 4, 5};
         
         // 调用方法并输出结果
         System.out.println(maxValue(n, V, v, w));
    }
}

4. 优化写法

除了二维写法，还有哪些优化手段？根据我从网上搜索到的信息，有以下几种可能的优化手段：

- 一种是使用一维数组来存储动态规划的状态，即只用一个数组f[j]来表示在容量为j下的最大价值。这样可以节省空间，但是需要注意遍历的顺序。对于完全背包问题，需要正序遍历容量，因为每种物品可以取无限次，所以可以利用已经更新过的状态。对于01背包问题，需要逆序遍历容量，因为每种物品只能取一次，所以要避免重复计算。
- 另一种是使用二进制优化的方法，即将每种物品拆分成若干个01背包问题。具体的做法是将每种物品的数量用二进制表示，然后按照二进制位的权重将物品分成若干份，每份的数量为2^k，其中k为二进制位的位置。例如，如果某种物品的数量为13，那么可以拆分成1,2,4,6四份，分别对应二进制位1101。这样就将一个完全背包问题转化为了多个01背包问题，然后按照01背包问题的方法求解即可。这样可以减少枚举的次数，提高效率。
- 还有一种是使用单调队列优化的方法，即利用一个单调递减的队列来维护状态转移过程中的最大值。具体的做法是将每种物品按照价值密度（即价值除以体积）从大到小排序，然后对于每种物品，用一个单调队列来存储其在不同容量下的最大价值，并保持队列中的元素递减。这样就可以在O(1)的时间内找到当前容量下的最大价值，并更新状态。这样可以避免重复计算和比较，提高效率。

4.1 使用一维数组来存储动态规划的状态

public class BackpackComplete {
    public static int maxValue(int n, int V, int[] v, int[] w) {
        // 动态规划数组
        int[] dp = new int[V + 1];
        // 初始化第一行为0
        for (int j = 0; j <= V; j++) {
            dp[j] = 0;
        }
        // 状态转移
        for (int i = 1; i <= n; i++) {
            for (int j = v[i - 1]; j <= V; j++) { // 正序遍历容量
                dp[j] = Math.max(dp[j], dp[j - v[i - 1]] + w[i - 1]); // 比较不装和装第i种物品的最大价值
            }
        }
        // 返回最大价值
        return dp[V];
    }
    
    public static void main(String[] args) {
        // 物品数量
        int n = 4;
        // 背包容量
        int V = 5;
        // 物品体积数组
        int[] v = {1, 2, 3, 4};
        // 物品价值数组
        int[] w = {2, 4, 4, 5};
        
        // 调用方法并输出结果
        System.out.println(maxValue(n, V, v, w));
    }
}

4.2 使用二进制优化的方法

import java.util.ArrayList;
import java.util.List;

public class BackpackCompleteBinary {
    public static int maxValue(int n, int V, int[] v, int[] w, int[] s) {
         // 动态规划数组
         int[] dp = new int[V + 1];
         // 初始化第一行为0
         for (int j = 0; j <= V; j++) {
             dp[j] = 0;
         }
         
         // 拆分物品并按照价值密度排序，这里省略排序的过程，假设已经排好序了
         List<Integer> newV = new ArrayList<>(); // 新的物品体积列表
         List<Integer> newW = new ArrayList<>(); // 新的物品价值列表
         
         for (int i = n - 1; i >= 0; i--) { // 假设从大到小排序，所以倒序遍历原数组
             int num = s[i]; // 第i种物品的数量
             for (int k = 1; k <= num; k <<= 1) { // 按照二进制位拆分物品，每次乘以2
                 num -= k; // 减去拆分出来的数量
                 newV.add(v[i] * k); // 加入新的物品体积列表
                 newW.add(w[i] * k); // 加入新的物品价值列表
             }
             if (num > 0) { // 如果还有剩余，就加入剩余的部分作为一个新的物品
                 newV.add(v[i] * num);
                 newW.add(w[i] * num);
             }
         }
         
         // 状态转移，和01背包问题一样，只是物品数量变多了
         for (int i = 0; i < newV.size(); i++) {
             for (int j = V; j >= newV.get(i); j--) { //逆序遍历容量
                 dp[j] = Math.max(dp[j], dp[j - newV.get(i)] + newW.get(i)); // 比较不装和装第i种物品的最大价值
             }
         }
         
          // 返回最大价值
          return dp[V];
    }
    
    public static void main(String[] args) {
         // 物品数量
         int n = 4;
         // 背包容量
         int V = 5;
         // 物品体积数组
         int[] v = {1, 2, 3, 4};
         // 物品价值数组
         int[] w = {2, 4, 4, 5};
         // 物品数量数组
         int[] s = {3, 1, 2, 1};
         
         // 调用方法并输出结果
         System.out.println(maxValue(n, V, v, w, s));
    }
}

4.3 使用单调队列优化的方法

import java.util.ArrayDeque;
import java.util.Deque;

public class BackpackCompleteQueue {
    public static int maxValue(int n, int V, int[] v, int[] w) {
         // 动态规划数组
         int[] dp = new int[V + 1];
         // 初始化第一行为0
         for (int j = 0; j <= V; j++) {
             dp[j] = 0;
         }
         
         // 按照价值密度排序，这里省略排序的过程，假设已经排好序了
         
         // 状态转移，利用单调队列维护最大值
         for (int i = n - 1; i >= 0; i--) { // 假设从大到小排序，所以倒序遍历原数组
             Deque<Integer> queue = new ArrayDeque<>(); // 创建一个单调队列，存储下标
             for (int j = 0; j < v[i]; j++) { // 遍历每个余数类别，即j % v[i]相同的容量
                 while (!queue.isEmpty() && j <= V) { // 如果队列不为空且容量不超过上限
                     while (!queue.isEmpty() && dp[j] >= dp[queue.peekLast()]) { // 如果队尾元素对应的价值小于等于当前价值，就弹出队尾元素，保持队列递减
                         queue.pollLast();
                     }
                     queue.offerLast(j); // 将当前下标加入队尾
                     dp[j] = dp[queue.peekFirst()] + (j - queue.peekFirst()) / v[i] * w[i]; // 更新当前容量下的最大价值，等于队首元素对应的价值加上额外放入的物品i的价值
                     j += v[i]; // 容量增加一个物品i的体积
                 }
                 if (!queue.isEmpty() && queue.peekFirst() == j - v[i] * (V / v[i] + 1)) { // 如果队首元素对应的容量已经超过了上限，就弹出队首元素
                     queue.pollFirst();
                 }
             }
         }
         
          // 返回最大价值
          return dp[V];
    }
    
    public static void main(String[] args) {
         // 物品数量
         int n = 4;
         // 背包容量
         int V = 5;
         // 物品体积数组
         int[] v = {1, 2, 3, 4};
         // 物品价值数组
         int[] w = {2, 4, 4, 5};
         
         // 调用方法并输出结果
         System.out.println(maxValue(n, V, v, w));
    }
}