编辑代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义物品结构体
struct Item {
    string name;
    int value;
    int weight;

    Item(string n, int v, int w) : name(n), value(v), weight(w) {}
};

// 动态规划函数
int knapsack(const vector<Item>& items, int capacity, vector<string>& selectedItems) {
    int n = items.size();
    
    // 初始化动态规划表
    vector<vector<int> > dp(n + 1, vector<int>(capacity + 1, 0));
    // 填充动态规划表
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= capacity; ++j) {
            if (items[i - 1].weight <= j) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - items[i - 1].weight] + items[i - 1].value);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // 回溯找到选择的物品
    int i = n;
    int j = capacity;
    while (i > 0 && j > 0) {
        if (dp[i][j] != dp[i - 1][j]) {
            selectedItems.push_back(items[i - 1].name);
            j -= items[i - 1].weight;
            i--;
        } else {
            i--;
        }
    }
    // 反转物品列表
    reverse(selectedItems.begin(), selectedItems.end());

    return dp[n][capacity];
}

int main() {
    // 定义物品数据
    vector<Item> items;
    items.push_back(Item("吉他", 1500, 1));
    items.push_back(Item("笔记本电脑", 2000, 3));
    items.push_back(Item("音响", 3000, 4));
    items.push_back(Item("iPhone", 2000, 1));

    // 背包容量
    int capacity = 4;

    // 存储选择的物品名称
    vector<string> selectedItems;

    // 调用动态规划函数求解背包问题
    int maxTotalValue = knapsack(items, capacity, selectedItems);

    // 输出选择的物品
    cout << "偷了如下物品：" << endl;
    for (int i = 0; i < selectedItems.size(); ++i) {
        cout << selectedItems[i] << endl;
    }

    // 输出总价值
    cout << "总价值" << maxTotalValue << endl;

    return 0;
}