编辑代码

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

using namespace std;

// 物品类
class Item {
public:
    string name;
    int value;
    int weight;

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

// 偷取物品函数
vector<Item> stealObject(int packCapacity, vector<Item>& items) {
    // 1. 找出子问题，确定表格的行和列
    int rowCount = items.size() + 1;
    int colCount = packCapacity + 1;
    
    // 2. 构建存储子问题的表格
    vector<vector<int>> dpArray(rowCount, vector<int>(colCount, 0));
    vector<Item> objectStolen; // 记录需要偷的东西

    // 表格清零
    for (int i = 0; i < rowCount; ++i) {
        fill(dpArray[i].begin(), dpArray[i].end(), 0);
    }

    // 3. 利用公式填充动态规划表
    for (int i = 1; i < rowCount; ++i) {
        for (int j = 1; j < colCount; ++j) {
            if (items[i - 1].weight <= j) {
                // 当前行对应的物品可以放入背包
                dpArray[i][j] = max(items[i - 1].value + dpArray[i - 1][j - items[i - 1].weight], dpArray[i - 1][j]);
            }
            else {
                // 当前行对应的物品不可以放入背包
                dpArray[i][j] = dpArray[i - 1][j];
            }
        }
    }

    // 4. 利用表格找出要放入物品
    int i = rowCount - 1;
    int j = colCount - 1;
    while (i > 0 && j > 0) {
        if (dpArray[i][j] != dpArray[i - 1][j]) {
            // 当前行对应的物品加入
            objectStolen.push_back(items[i - 1]);
            j = j - items[i - 1].weight; // 减去放入包的当前剩余的重量
            i = i - 1;
        }
        else {
            // 当前行对应的物品不被放入背包
            i = i - 1;
        }
    }

    return objectStolen;
}

void test() {
    vector<Item> items = {
        Item("故宫", 7, 1),
        Item("颐和园", 8, 2),
        Item("长城", 9, 3),
        Item("天坛", 6, 1)
    };

    vector<Item> objectInPack = stealObject(4, items);

    int maxValue = 0;

    cout << "途径以下景点：" << endl;
    for (const Item& item : objectInPack) {
        maxValue += item.value;
        cout << item.name << endl;
    }

    cout << "总评分：" << maxValue << endl;
}

int main() {
    test();
    return 0;
}