动态规划之01背包问题思路详细讲解

动态规划之01背包问题思路详细讲解

引用

CSDN

1.

https://m.blog.csdn.net/2301_81811979/article/details/136750429

01背包问题定义

01背包问题是指：有n种重量或价值不同的物体，每种物体只有1个。使用一个容量为m的背包去装这些物体，问能装到的最大价值为多少？

样例说明

假设我们有以下物品：

背包容量为4。

动态规划解法

1. DP数组的含义

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少 。

i，j，以及dp[i][j]所存的值便包含了每个物体，背包容量，而物体的重量与价值也间接的与j，dp[i][j]挂钩。

2. 确定递推公式

以本例的最终值dp[2][4]为例，首先以物品二的上面几行为基准，他们表示在下标为【0到1】的物品中对应不同j值是取得的最大值，但本体最终是要扩充到下标为【0到2】的物品中去，所以我们可以得到如下表达式：（因为dp数组中i的定义为[0到i],并不是说第i行就必须会被选中，所以此时物体2便有两种状态）

• 不放物品2 ：dp[2][4] 由dp[1][4]推出，即背包容量为4，里面不放物品2的最大价值，此时 dp[2][4] 就是dp[1][4]。其实就是a.当物品i的重量大于背包j的重量b.单纯不装（后面代码中会有相应对应点）时，物品i无法放进背包中，所以背包内的价值依然和前面相同。
• 放物品2 ：由dp[1][0]]推出，dp[1][0]+value[2]为背包容量为0的时侯放物品2的最大价值，那么dp[1][0]]就是背包放物品2得到的价值

递推公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. 确定dp数组的初始值以及遍历顺序

由dp数组的定义可得到第一行的每个值，很好理解，第一列也可视为放不下物品i是由递推式dp[i - 1][j]得到，因为背包容量为0真的装不下

遍历顺序：因为由上述分析得下一行总由上一行得出，所以我们一行一行来递推，直到最后一行，得到最后一格对应得最终值

for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

4. 最终代码

void test_2_wei_bag_problem1() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagweight = 4;

    // 二维数组
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

    // 初始化
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }

    // weight数组的大小 就是物品个数
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

        }
    }

    cout << dp[weight.size() - 1][bagweight] << endl;
}

int main() {
    test_2_wei_bag_problem1();
}

最后解释的一点：因为每一步递推的上一步已经求得了最大值，所以最后一定为最大值板上钉钉