背包

背包问题

01背包

一定容量的背包所能装下的最大物品价值。

对于每个物品，选与不选两个状态，取最大值。

先遍历物品，再遍历容量。如果是一维数组

  • 注意01背包是从后遍历来防止重复选物品。
  • 完全背包就从物品的容量开始，到最大容量，即可以重复选。

经典

变式

多维01背包

进阶

多重背包

相同物品有多件。是特殊01背包。加一个循环遍历相同物品个数。

完全背包

在元素可以重复添加的条件下，能装下的最大物品价值、硬币兑换最小次数、子串是否能组成字符串等。

例子

求[1,2,3]组成4的种类

组合:[1,1,1,1],[1,1,2],[2,2],[1,3]

像是后面的物品把前面的物品包含了进去，一轮循环考虑一个物品。

排列: [1,1,1,1],[1,1,2],[1,2,1],[1,3],[2,1,1],[2,2],[3,1]

_像是随机替换，一轮可以替换多个物品_。

组合

排列

组合不考虑元素顺序，排列考虑。

进阶

记录路径：记录选择了哪些物品

01背包记录路径

01背包，物品有多种选择，不同选择花销不同，收获不同。

// n个题，限定t时间，在限定时间内拿到更高的分，返回每个题的做法。
// F代表不做，获得0分；
// B代表暴力算法，花费force[i].first时间，获得force[i].second分；
// C代表完美通过，花费perfect[i].first时间，获得perfect[i].second分；
// 其实是01背包，每种物品有三种选择，path记录时，多判断一个状态即可。
// 通过逆序查找来查找路径。
string GetMaxScoreStrategy(int n, int t, vector<pair<int, int>>& force, vector<pair<int, int>>& perfect) {
    vector<vector<char>> path(n + 1, vector<char> (t + 1, 'F'));
    vector<vector<int>> dp(n + 1, vector<int> (t + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= t; ++j) {
            // 不做
            dp[i][j] = dp[i - 1][j];

            // 判断暴力算法
            int currTime = force[i - 1].first, currScore = force[i - 1].second;
            if (currTime <= j && dp[i][j] < dp[i - 1][j - currTime] + currScore) {
                dp[i][j] = dp[i - 1][j - currTime] + currScore;
                path[i][j] = 'B';
            }
            
			// 判断完美算法
            currTime = perfect[i - 1].first, currScore = perfect[i - 1].second;
            if (currTime <= j && dp[i][j] < dp[i - 1][j - currTime] + currScore) {
                dp[i][j] = dp[i - 1][j - currTime] + currScore;
                path[i][j] = 'A';
            }
        }
    }

    int currTime = t, currIndex = n;
    string res(n, 'F'); // 默认不做
    while (currIndex > 0 && currTime > 0) { // 为0时，为初始状态，无背包或者时间，无需计算。
        switch (path[currIndex][currTime]) {
            case 'F': break; //noting. 默认就是不做。
            case 'A':
                currTime -= perfect[currIndex - 1].first;
                res[currIndex - 1] = 'A';
                break;
            case 'B':
                currTime -= force[currIndex - 1].first;
                res[currIndex - 1] = 'B';
                break;
        }
        --currIndex;
    }
    return res;
}

完全背包记录记录

其他背包进阶

背包9讲

LeetCode > Dynamic Programming
背包
https://messenger1th.github.io/2024/07/24/LeetCode/Dynamic Programming/背包/
作者
Epoch
发布于
2024年7月24日
许可协议