编辑代码

#include <iostream>  
#include <vector>  
#include <algorithm>  
  
using namespace std;  
  
vector<int> knapsack(int W, int n, vector<int>& w, vector<int>& v) {  
    vector<long long> dp(W + 1, 0);  
  
    for (int i = 0; i < n; ++i) {  
        for (int j = w[i]; j <= W; ++j) { // 注意这里改为从w[i]开始  
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);  
        }  
    }  
  
    int max_value = dp[W];  
  
    vector<int> solution;  
    int remaining_weight = W;  
    for (int i = n - 1; i >= 0; --i) { // 从后向前遍历物品  
        while (remaining_weight >= w[i] && dp[remaining_weight] == dp[remaining_weight - w[i]] + v[i]) {  
            solution.push_back(i + 1); // 物品编号从1开始  
            remaining_weight -= w[i];  
            // 这里不需要计算数量，因为我们每次只添加一个物品  
        }  
    }  
  
    // 输出结果  
    cout << "最优解：" << endl;  
    cout << "总价值=" << max_value << ";" << endl;  
    cout << "方案：";  
    for (int i = solution.size() - 1; i >= 0; --i) { // 从后向前输出，以便顺序与题目要求一致  
        int count = 1; // 初始假设只选择一个物品  
        if (i < solution.size() - 1) {  
            // 计算相同物品连续选择的数量（如果有的话）  
            while (i > 0 && solution[i] == solution[i - 1]) {  
                --i;  
                ++count;  
            }  
        }  
        cout << "物品" << solution[i] << "共" << count << "件，";  
    }  
    cout << endl; // 注意在循环外添加换行符  
  
    return solution;  
}  
  
int main() {  
    int W = 7; // 背包容量  
    int n = 3; // 物品数量  
    vector<int> w = {3, 4, 2}; // 物品重量  
    vector<int> v = {4, 5, 3}; // 物品价值  
  
    vector<int> result = knapsack(W, n, w, v);  
  
    return 0;  
}