基于动态规划的0-1背包问题解决方案

#include 
#include 

using namespace std;

// 定义物品结构体
struct Item {
    int weight; // 物品重量
    int value; // 物品价值
};

// 使用动态规划解决0-1背包问题
int knapsack(int capacity, vector& items) {
    int n = items.size();
    // 创建一个二维数组 dp，用于存储子问题的解
    // dp[i][j] 表示考虑前 i 个物品，背包容量为 j 时所能获得的最大价值
    vector> dp(n + 1, vector(capacity + 1, 0));

    // 填充 dp 数组
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= capacity; ++j) {
            // 如果当前物品的重量超过背包容量，则不装入该物品
            if (items[i - 1].weight > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                // 否则，选择装入或不装入该物品，取两者中价值更大的方案
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - items[i - 1].weight] + items[i - 1].value);
            }
        }
    }

    // 返回 dp 数组的右下角元素，即为问题的最优解
    return dp[n][capacity];
}

int main() {
    // 定义背包容量和物品列表
    int capacity = 10;
    vector items = {
        {2, 6},
        {2, 3},
        {6, 5},
        {5, 4},
        {4, 6}
    };

    // 调用 knapsack 函数计算最大价值
    int maxValue = knapsack(capacity, items);

    // 输出结果
    cout << "最大价值: " << maxValue>

这段代码清晰地展示了如何使用动态规划解决0-1背包问题。它首先定义了一个物品结构体，然后实现了 knapsack 函数，该函数使用动态规划算法计算背包所能容纳的最大价值。最后，在 main 函数中定义了背包容量和物品列表，并调用 knapsack 函数计算结果。