动态规划-01背包

01 背包问题

物品价值: 5, 10, 3, 6, 3
物品重量: 2, 5, 1, 4, 3
背包容量: 6

下标	0	1	2	3	4
价值	5	10	3	6	3
重量	2	5	1	4	3

物品 \ 背包容量	1	2	3	4	5	6
0	0	0	0	0	0	0
1	0	5	5	5	5	5
2	0	5	5	5	10	10
3	3	5	8	8	10	13
4	3	5	8	8	10	13
5	3	5	8	8	10	13

说明：

dp表格中存在i=0的行，表示不选任何物品，dp的行数为物品数量+1，因此在获取物品价值与物品重量的时候需要下标i-1
行: 表示前 i 个物品（下标<=i-1）（物品编号从 0 到 5）
列: 表示背包容量 j（容量从 0 到 6）
dp[i][j]: 表示考虑前 i 个物品（下标<=i-1），在背包容量为 j 时的最大价值

思路

往dp表格中计算填写值。

装不下，即j<weights[i - 1]：直接上一行的值dp[i][j]=dp[i-1][j]
装得下，即j>=weights[i - 1]：需要考虑装不装[i-1]这个物品，要比较装这一项的最大价值与不装这一项的最大价值，计算最大值(装它，不装它)=max(value[i-1]+还能装的价值,dp[i-1][j])，还能装的价值=dp[i-1][j-weights[i-1]]=max(value[i-1]+dp[i-1][j-weights[i-1]],dp[i-1][j])

最后的结果在 dp[5][6]，即最大价值为 13。

cpp代码实现

#include <iostream>
#include <algorithm>
#include <vector>
int knapsack(int capacity, const std::vector<int> &weights, const std::vector<int> &values)
{
    int n = weights.size();
    // 使用 std::vector 创建二维 DP 表，初始化为 0
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, 0));

    // 填充 DP 表
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= capacity; ++j)
        {
            if (weights[i - 1] <= j)
            {
                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
            std::cout << dp[i][j] << " ";
        }
        std::cout << std::endl;
    }

    // 返回 DP 表中最后一个格子的值，即为最大价值
    return dp[n][capacity];
}

int main()
{
    std::vector<int> values = {5, 10, 3, 6, 3};
    std::vector<int> weights = {2, 5, 1, 4, 3};
    int capacity = 6;

    int max_value = knapsack(capacity, weights, values);
    std::cout << "Maximum value in knapsack = " << max_value << std::endl;

    return 0;
}

cpp空间优化


int knapsack_new(int capacity, const std::vector<int> &weights, const std::vector<int> &values)
{
    int n = weights.size();
    // 创建两个一维 DP 数组
    std::vector<int> dp_prev(capacity + 1, 0);
    std::vector<int> dp_curr(capacity + 1, 0);

    // 填充 DP 表
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= capacity; ++j)
        {
            if (weights[i - 1] <= j)
            {
                dp_curr[j] = std::max(dp_prev[j], dp_prev[j - weights[i - 1]] + values[i - 1]);
            }
            else
            {
                dp_curr[j] = dp_prev[j];
            }
            std::cout << dp_curr[j] << " ";
        }
        std::cout << std::endl;
        // 更新 dp_prev 为 dp_curr 的值
        std::swap(dp_prev, dp_curr);
    }

    // 返回 DP 表中最后一个格子的值，即为最大价值
    return dp_prev[capacity];
}