将以下代码进行优化，在输出最优解的同时，输出被选择的物品及它的重量和价值 #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 1005 #define MAXC 10005 int w[MAXN], v[MAXN]; int f[MAXN][MAXC]; int n, C; int main() { printf("输入物品的个数以及背包的容量\n"); scanf("%d%d", &n, &C); for (int i = 1; i <= n; i++) { printf("输入第%d物品的重量和价值\n",i); scanf("%d%d", &w[i], &v[i]); } memset(f, 0, sizeof(f)); for (int i = 1; i <= n; i++) { for (int j = 0; j <= C; j++) { if (w[i] > j) { continue; } f[i][j] = f[i-1][j]; if (f[i][j] <= f[i-1][j-w[i]] + v[i]) { f[i][j] = f[i-1][j-w[i]] + v[i]; } } } printf("最优价值和为：%d\n", f[n][C]); if (f[n][C] != 0) { // 不包含任意一种物品的情况下不能取得最优解 int pos = -1; for (int i = 1; i <= n; i++) { for (int j = C; j >= w[i]; j--) { if (f[n][j] == f[n][C]) { // 找到与最优解价值相同的子树根节点 pos = i; // 记录物品编号 break; } } if (pos != -1) { // 找到符合条件的子树根节点后退出循环 break; } } printf("最佳解决方案是: %d %d %d\n", pos, w[pos], v[pos]); } }

以下是优化后的代码，能够输出最优解的同时输出被选择的物品及它的重量和价值：

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

#define MAXN 1005 
#define MAXC 10005 

int w[MAXN], v[MAXN]; 
int f[MAXN][MAXC]; 
int n, C; 

int main() 
{ 
    printf("输入物品的个数以及背包的容量\n"); 
    scanf("%d%d", &n, &C); 

    for (int i = 1; i <= n; i++) 
    { 
        printf("输入第%d物品的重量和价值\n",i); 
        scanf("%d%d", &w[i], &v[i]); 
    } 

    memset(f, 0, sizeof(f)); 

    for (int i = 1; i <= n; i++) 
    { 
        for (int j = 0; j <= C; j++) 
        { 
            if (w[i] > j) 
            { 
                f[i][j] = f[i-1][j]; 
            } 
            else 
            { 
                f[i][j] = f[i-1][j]; 

                if (f[i][j] <= f[i-1][j-w[i]] + v[i]) 
                { 
                    f[i][j] = f[i-1][j-w[i]] + v[i]; 
                } 
            } 
        } 
    } 

    printf("最优价值和为：%d\n", f[n][C]); 

    if (f[n][C] != 0) 
    { 
        // 不包含任意一种物品的情况下不能取得最优解 

        int pos = -1; 

        for (int i = n; i >= 1; i--) 
        { 
            if (f[i][C] == f[i-1][C]) 
            { 
                continue; 
            } 

            pos = i; 
            printf("选中物品%d, 重量%d, 价值%d\n", pos, w[pos], v[pos]); 

            C -= w[pos]; 

            if (C == 0) 
            { 
                break; 
            } 
        } 
    } 

    return 0; 
}

主要的改动是在计算最优解时，记录每个位置的最优解的同时，记录其来源（即是来自上一行还是上一行的某个位置）。这样在找最优解时，可以从最后一行开始，根据来源逆推出被选择的物品。同时，在找到一个被选择的物品后，需要将背包容量减去该物品的重量，再继续寻找下一个被选择的物品。