编辑代码

#include <iostream>
#include <algorithm>
#include <cstring> 

using namespace std;


struct Item {
    int weight;
    int value;
    char name[50]; 
};


int knapsack(Item items[], int n, int capacity) {
    int dp[n + 1][capacity + 1];

    // 初始化动态规划表
    for (int i = 0; i <= n; ++i) {
        for (int w = 0; w <= capacity; ++w) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            } else if (items[i - 1].weight <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - items[i - 1].weight] + items[i - 1].value);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    // 输出选择的商品名字
    int w = capacity;
    for (int i = n; i > 0 && w > 0; --i) {
        if (dp[i][w] != dp[i - 1][w]) {
            cout << "Selected item: " << items[i - 1].name << endl;
            w -= items[i - 1].weight;
        }
    }

    // 返回最优解（背包中物品的最大总价值）
    return dp[n][capacity];
}

int main() {
  
    Item items[] = {{3, 5000, "相机"}, {2, 3000, "手机"}, {5, 6000, "笔记本电脑"}};

    
    int n = sizeof(items) / sizeof(items[0]);

    // 背包容量
    int capacity = 5;

    // 求解背包问题
    int maxValue = knapsack(items, n, capacity);

    // 输出结果
    cout << "最大价值为: " << maxValue << endl;

    return 0;
}