使用C++写一个动态规划中背包问题的模板

好的，下面是使用 C 语言实现动态规划中背包问题的模板：

#include <stdio.h>

int max(int a, int b)
{
    return a > b ? a : b;
}

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]); // 物品的数量

    int result = Knapsack(W, wt, val, n);
    printf("背包能装下的最大价值为：%d\n", result);

    return 0;
}

这个模板的实现思路是，建立一个二维的 dp 数组，其中 dp[i][w] 表示前 i 个物品在背包承重为 w 时，能装下的最大价值。当第 i 个物品的重量小于等于背包剩余承重时，有两种选择：选或不选。如果选的话，则能装下的最大价值为第 i 个物品的价值加上前 i - 1 个物品在背包剩余承重为 w - wt[i - 1] 时能装下的最大价值（dp[i - 1][w - wt[i - 1]]）；如果不选的话，则能装下的最大价值为前 i - 1 个物品在背包剩余承重为 w 时能装下的最大价值（dp[i - 1][w]）。如果第 i 个物品的重量大于背包剩余承重，那么就不能选。最终返回 dp[n][W]，即前 n 个物品在背包最大承重为 W 时能装下的最大价值。