01背包问题-【动态规划/背包问题】背包问题第一阶段最终章：混合背包问题

前言

今天是我们讲解动态规划专题中的「背包问题」的第十一篇。

今天将会学习「混合背包」问题，同时也是我们「背包问题」的第一阶段的最后一节。

今天首先会和大家回顾之前学过的三种背包问题。

然后通过一道「混合背包」问题，来将我们之前学的几种背包问题串联起来。

希望通过本篇内容01背包问题，大家会对背包问题有更清晰的认识。

另外，我在文章结尾处列举了我所整理的关于背包问题的相关题目。

背包问题我会按照编排好的顺序进行讲解（每隔几天更新一篇，确保大家消化）。

你也先可以尝试做做，也欢迎你向我留言补充，你觉得与背包相关的 DP 类型题目 ~

回顾三种传统背包问题

前面我们已经学完了三种传统背包问题了。

这里再回顾一下三种传统背包：

三种背包问题的「难易程度」是「递增」，但「重要程度」则是「递减」的。

虽然「多重背包」的和都比较 trick。

但其实「多重背包」并没有这么常见，以至于在上我都没找到与「多重背包」相关的题目。

同时三种背包问题都有「不超过」和「恰好」两种状态定义。

这两种状态定义只在「初始化」上有区别。

至于该如何初始化则要抓住什么样的状态是合法的：

总的来说，三种背包问题都很经典（本质上都是组合优化问题），以至于「背包问题」直接成为了一类的动态规划模型。

我的建议是三种背包都需要掌握。但如果实在要分侧重点的话，我更愿意你将大多数时间花在「01 背包」和「完全背包」上。

混合背包

给定物品数量和背包容量。第件物品的体积是，价值是，可用数量为：

求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本分析

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

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

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

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

代码：

class Solution {
    public int maxValue(int N, int C, int[] w, int[] v, int[] s) {
        // 构造出物品的「价值」和「体积」列表
        List worth = new ArrayList();
        List volume = new ArrayList();
        for (int i = 0; i < N; i++) {
            int type = s[i];
            
            // 多重背包：应用「二进制优化」转换为 0-1 背包问题
            if (type > 0) { 
                for (int k = 1; k <= type; k *= 2) {
                    type -= k;
                    worth.add(w[i] * k);
                    volume.add(v[i] * k);
                }
                if (type > 0) {
                    worth.add(w[i] * type);
                    volume.add(v[i] * type);
                }
                
            // 01 背包：直接添加
            } else if (type == -1) {
                worth.add(w[i]);
                volume.add(v[i]);
                
            // 完全背包：对 worth 做翻转进行标记
            } else {
                worth.add(-w[i]);
                volume.add(v[i]);
            }
        }
        
        // 使用「一维空间优化」方式求解三种背包问题
        int[] dp = new int[C + 1];
        for (int i = 0; i < worth.size(); i++) {
            int wor = worth.get(i);
            int vol = volume.get(i);
            
            // 完全背包：容量「从小到大」进行遍历
            if (wor < 0) { 
                for (int j = vol; j <= C; j++) {
                    // 同时记得将 worth 重新翻转为正整数
                    dp[j] = Math.max(dp[j], dp[j - vol] - wor); 
                }
                
            // 01 背包：包括「原本的 01 背包」和「经过二进制优化的完全背包」
            // 容量「从大到小」进行遍历
            } else { 
                for (int j = C; j >= vol; j--) {
                    dp[j] = Math.max(dp[j], dp[j - vol] + wor);
                }
            }
        }
        return dp[C];
    }
}