编辑代码

#include <stdio.h>
#include <wchar.h>

#define N 4 // 物品个数
#define W 4 // 背包承重量

int weights[N] = {4, 3, 1, 2}; // 物品重量
int values[N] = {3000, 2000, 1500, 2000}; // 物品价值

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

int knapsack(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 (weights[i - 1] <= w) {
                if (values[i - 1] + dp[i - 1][w - weights[i - 1]] > dp[i - 1][w]) {
                    dp[i][w] = values[i - 1] + dp[i - 1][w - weights[i - 1]];
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[N][W];
}

void printSelectedItems(int dp[N + 1][W + 1]) {
    int i = N;
    int w = W;
    printf("背包中包含的物品有：\n");

    while (i > 0 && w > 0) {
        if (dp[i][w] != dp[i - 1][w]) {
            printf("物品%d（重量：%d，价值：%d）\n", i, weights[i - 1], values[i - 1]);
            w -= weights[i - 1];
        }
        --i;
    }
}

int main() {
    int dp[N + 1][W + 1];
    printf("背包中的最大价值：%d\n", knapsack(dp));
    printSelectedItems(dp);
    return 0;
}