混合背包问题

短命女 2024-03-26 17:58 66阅读 0赞

![7f24232b13374c079792989977bbe1b6.png][]

![fef68ba80f464746b8e546b6aa72285b.png][] 混合背包其实就是综合了「01 背包」、「完全背包」和「多重背包」三种传统背包问题。

我们知道在一维空间优化方式中「01 背包」将当前容量 按照“从大到小”进行遍历，而「完全背包」则是将当前容量 按照“从小到大”进行遍历。

同时「多重背包」可以通过「二进制优化」彻底转移成「01 背包」。

所以我们只需要根据第 个物品是「01 背包」物品还是「完全背包」物品，选择不同的遍历顺序即可。

import java.util.ArrayList;
    import java.util.List;
    
    public class MixBag {
    
        public int maxValue(int n, int c, int[] v, int []w, int[]s ) {
            //首先建立完全背包内容的二进制化
            //拆分后的价值表
            List<Integer> val = new ArrayList<>();
            //拆分后的体积表
            List<Integer> vol = new ArrayList<>();
    
            int [] dp = new int[c + 1];
            for (int i = 0; i < s.length; i++) {
                int type = s[i];
                if (type > 0) {
                    //说明是有使用次数的多重背包问题
                    //多重背包问题将其二进制化
    
                    for (int j = 1; j <= type; j *= 2) {
                        type -= j;
                        val.add(j * v[i]);
                        vol.add(j * w[i]);
                    }
                    //如果不是恰好拆分成全部的二进制
                    if (type > 0) {
                        val.add(type * v[i]);
                        vol.add(type * w[i]);
                    }
                } else if (type == 0) {
                    //无限制数量，证明是完全背包
                    //因为完全背包的一维度遍历顺序和0/1以及多重背包的顺序不同
                    //所以将val设置为负数
                    val.add(-v[i]);
                    vol.add(w[i]);
                } else {
                    // 0/1背包
                    val.add(v[i]);
                    vol.add(w[i]);
                }
            }
            //二进制处理完毕
    
            for (int i = 0; i < val.size() ; i++) {
                int curVal = val.get(i);
                int curWei = vol.get(i);
                if (curVal > 0){
                    //01背包或者是多重背包，但是多重背包已经被压缩，可以当成01处理
                    for (int j = c; j >= curWei ; j--) {
                        dp[j] = Math.max(dp[j], dp[j - curWei] + curVal);
                    }
                }
                else{
                    //完全背包
                    for(int j = curWei; j <= c ; j++){
                        //减号是因为此时由于是完全背包，所以val存的是负值
                        dp[j] = Math.max(dp[j], dp[j-curWei] - curVal);
                    }
                }
            }
            return dp[c];
        }
    }

[7f24232b13374c079792989977bbe1b6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/505ec91b3eab4e8abd1d2601e80303f0.png
[fef68ba80f464746b8e546b6aa72285b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/fc53a479f53d4c179852956f590c362c.png