C语言实现背包问题：如何输出背包中物品的名称

要输出放入背包的物品名称，核心是通过回溯DP表逆向推导哪些物品被选中，具体逻辑如下：

• 对比DP[i][j]与DP[i-1][j]：若前者更大，说明第i个物品被放入背包，此时将背包容量减去该物品重量，继续回溯前i-1个物品；
• 若两者相等，说明第i个物品未被选中，直接回溯前i-1个物品。

以下是修改后的完整代码：

#include <stdio.h>
#include <string.h>

#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int DP[103][100003];
int w[103]; // 物品重量
int v[103]; // 物品价值
char item_names[103][11]; // 存储物品名称，索引与物品DP索引对应

int main() {
    int n, k; // n=物品数量，k=背包容量
    printf("输入物品数量和背包容量：");
    scanf("%d %d", &n, &k); 

    printf("\n输入每个物品的名称、重量、价值：\n");
    for (int i = 1; i <= n; i++) {
        scanf("%s %d %d", item_names[i], &w[i], &v[i]);
    }

    // 0-1背包DP计算
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            if (j >= w[i]) {
                DP[i][j] = MAX(DP[i - 1][j], DP[i - 1][j - w[i]] + v[i]);
            } else {
                DP[i][j] = DP[i - 1][j];
            }
        }
    }

    printf("\n最大价值：%d\n", DP[n][k]);

    // 回溯找出选中的物品
    printf("放入背包的物品：\n");
    int current_cap = k;
    for (int i = n; i >= 1; i--) {
        if (DP[i][current_cap] != DP[i-1][current_cap]) {
            printf("- %s\n", item_names[i]);
            current_cap -= w[i];
            if (current_cap == 0) break;
        }
    }

    return 0;
}

关键修改说明 #

1. 调整物品名称数组索引，使其与DP表的物品索引（从1开始）对应，避免回溯时的索引混乱；
2. 添加回溯逻辑：从最后一个物品和最大背包容量开始逆向遍历，通过DP值的差异判断物品是否被选中，同时更新剩余背包容量；
3. 格式化输出选中的物品名称，结果更清晰直观。

内容的提问来源于stack exchange，提问作者HCyan