#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;
}