用c++实现0-1背包的动态规划算法

以下是用C++实现0-1背包问题的动态规划算法：

#include <iostream>
#include <algorithm>
using namespace std;

// 0-1背包问题的动态规划算法
int knapsack(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1]; // dp[i][j]表示前i个物品，重量不超过j的最大价值
    for(int i=0; i<=n; i++) {
        for(int j=0; j<=W; j++) {
            if(i==0 || j==0) { // 边界条件
                dp[i][j] = 0;
            } else if(wt[i-1] > j) { // 当前物品的重量大于背包容量，不能选
                dp[i][j] = dp[i-1][j];
            } else { // 能选则判断选或不选哪个更优
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]]+val[i-1]);
            }
        }
    }
    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) << endl;
    return 0;
}

其中，`dp[i][j]`表示前i个物品，重量不超过j的最大价值。边界条件为`dp[0][j]=0`和`dp[i][0]=0`，表示没有物品或背包容量为0时，最大价值为0。当第i个物品的重量大于背包容量j时，不能选，因此价值就是上一个最优解`dp[i-1][j]`；否则，当前物品可以选或不选，选或不选哪个更优就是判断`dp[i-1][j]`和`dp[i-1][j-wt[i-1]]+val[i-1]`两者之间的大小关系。最终的结果就是`dp[n][W]`，即前n个物品，重量不超过W的最大价值。