多重背包问题中的二进制状态压缩

r囧r小猫 2024-03-26 17:57 41阅读 0赞

## 1.多重背包问题 ##

![34a8d39916ef4ea98912f3266ca60ced.png][]

经典的多重背包问题和01背包问题的相似之处在于二者的一维遍历顺序都是从右侧往左侧遍历。

同时多重背包的一维写法不比二维写法降低时间复杂度。

## 2.多重背包标准写法:(平铺展开形式） ##

class Solution {
        public int maxValue(int N, int C, int[] s, int[] v, int[] w) {
            int[] dp = new int[C + 1];
            for (int i = 0; i < N; i++) {
                for (int j = C; j >= v[i]; j--) {
                    for (int k = 0; k <= s[i] && j >= k * v[i]; k++) {
                        dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]);
                    }
                }
            }
            return dp[C];
        }
    }

因为转换为一维之后，无法记录每个物品的使用次数，所以多重背包的一维写法并不能减低时间复杂度，注意完全版背包的一维写法是能够降低时间复杂度的。此处的代码与01背包十分相似。01背包的代码如下:

class Solution {
        public int maxValue(int N, int C, int[] v, int[] w) {
            int[] dp = new int[C + 1];
            for (int i = 0; i < N; i++) {
                for (int j = C; j >= v[i]; j--) {
                    // 不选该物品
                    int n = dp[j]; 
                    // 选择该物品
                    int y = dp[j-v[i]] + w[i]; 
                    dp[j] = Math.max(n, y);
                }
            }
            return dp[C];
        }
    }

## 3.二进制压缩形式的多重背包 ##

上述的多重背包的解法实际上是将带选择的m个物品平着展开为\[1,1,1....\](共计m个），具体可以查看最后一个for循环的写法，不断尝试一个一个的将数据加进去。

实际上这种解法只能解决数据量为平方级别的数据。而二进制解法则是将原本为 n 的物品用 ceil(log(n)) 个数来代替，从而降低算法复杂度。

学过 Linux 的都知道文件权限最高是 7，代表拥有读、写、执行的权限，但其实这个 7 是对应了 1、2、4 三个数字的，也就是 `r:1`、`w:2`、`x:4` ，三种权限的组合共有 8 种可能性

7 可以用 `1、2、4` 来代替，像刚刚提到的 10 ，我们可以使用 `1、2、4、3` 来代替，你可能会有疑问，为什么是 `1、2、4、3`，而不是 `1、2、4、6` 或者 `1、2、4、8` 呢？

其实把他们几个数加起来就知道了，`1、2、4、6` 可以表达的范围是 0~13，而 `1、2、4、8` 可以表达的范围是 0~15，而我们要求的是表达 10，大于 10 的范围是不能被选择的。

所以我们可以在 `1、2、4` （表达的范围是 0~7）的基础上，增加一个数 3（由 10 - 7 而来），这样就能满足我们需要表达的范围 0~10。

具体的转换为二进制的代码如下所示：

class Solution {
        public int maxValue(int N, int C, int[] s, int[] v, int[] w) {
            // 扁平化
            List<Integer> worth = new ArrayList<>();
            List<Integer> volume = new ArrayList<>();
    
            // 我们希望每件物品都进行扁平化，所以首先遍历所有的物品
            for (int i = 0; i < N; i++) {
                // 获取每件物品的出现次数
                int val = s[i];
                // 进行扁平化：如果一件物品规定的使用次数为 7 次，我们将其扁平化为三件物品：1*重量&1*价值、2*重量&2*价值、4*重量&4*价值
                // 三件物品都不选对应了我们使用该物品 0 次的情况、只选择第一件扁平物品对应使用该物品 1 次的情况、只选择第二件扁平物品对应使用该物品 2 次的情况，只选择第一件和第二件扁平物品对应了使用该物品 3 次的情况 ... 
                //注意此处是等号，可能正好减完
                for (int k = 1; k <= val; k *= 2) { 
                    val -= k;
                    worth.add(w[i] * k);
                    volume.add(v[i] * k);
                }
                if (val > 0) {
                    //没有正好减完
                    worth.add(w[i] * val);
                    volume.add(v[i] * val);
                }
            }
    
            // 0-1 背包问题解决方案
            int[] dp = new int[C + 1];
            for (int i = 0; i < worth.size(); i++) {
                for (int j = C; j >= volume.get(i); j--) {
                    dp[j] = Math.max(dp[j], dp[j - volume.get(i)] + worth.get(i));
                }
            }
            return dp[C];
        }
    }

[34a8d39916ef4ea98912f3266ca60ced.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c097f7cf648b442cadc8ca6e860c3bd2.png