编辑代码

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

using namespace std;

struct Fruit {
    string name;
    int weight;
    int value;
};

void maxBackpackByValue(int num, vector<Fruit>& fruits) {
    int size = fruits.size();
    vector<vector<int>> dp(size+1, vector<int>(num+1, 0));
    vector<vector<int>> selected(size+1, vector<int>(num+1, 0));
    
    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= num; j++) {
            if (fruits[i-1].weight <= j) {
                int value1 = fruits[i-1].value + dp[i-1][j-fruits[i-1].weight];
                int value2 = dp[i-1][j];
                if (value1 > value2) {
                    dp[i][j] = value1;
                    selected[i][j] = 1;
                } else {
                    dp[i][j] = value2;
                    selected[i][j] = 0;
                }
            } else {
                dp[i][j] = dp[i-1][j];
                selected[i][j] = 0;
            }
        }
    }
    
    int maxValue = dp[size][num];
    int maxValuePos = 0;
    for (int i = 1; i <= size; i++) {
        if (selected[i][num] == 1) {
            maxValuePos |= (1 << (i-1));
        }
    }
    
    int sum = 0;
    for (int i = 0; i < size; i++) {
        if ((maxValuePos >> i) & 1) {
            cout << fruits[i].name << endl;
            sum += fruits[i].value;
        }
    }
    
    cout << "总价值:" << sum << endl;
}

int main() {
    vector<Fruit> fruits = {
        {"苹果", 15, 300},
        {"香蕉", 18, 180},
        {"橘子", 10, 150},
        {"猕猴桃", 9, 270}
    };
    
    cout << "装水果的策略:" << endl;
    maxBackpackByValue(20, fruits);
    
    return 0;
}