背包问题的动态规划算法实现c++代码

背包问题是一个经典的动态规划问题，通常涉及选择物品放入背包以最大化价值，而每个物品都有自己的重量限制。下面是一个简单的C++代码实现，用于解决0-1背包问题：

#include <iostream>
using namespace std;

int knapsack(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1];

    // 初始化动态规划表
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                dp[i][w] = 0;
            else if (wt[i-1] <= w)
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);  // 选择物品
            else
                dp[i][w] = dp[i-1][w];  // 不选择物品
        }
    }

    return dp[n][W];
}

int main() {
    int W = 50;  // 背包容量
    int wt[] = {10, 20, 30};  // 物品重量
    int val[] = {60, 100, 120};  // 物品价值
    int n = sizeof(wt) / sizeof(wt[0]);

    cout << "最大价值: " << knapsack(W, wt, val, n);

    return 0;
}

这个代码首先创建了一个二维数组dp，然后通过迭代计算每个状态下的最优解。对于每个物品，它会判断是否应该包含它（如果当前物品的重量小于等于剩余背包容量），并选择价值更高的一种策略。