用c++写代码 超市现有若干物品,每种物品都只有一包,包装规格(重量)和整包价格如:食盐每包10斤(50元/包)、白糖每包8斤(46元/包)、大米每包20斤(60元/包),等,现有一个手推车载重m斤,上述物品每样都可以按所需的重量单独打包,包装袋重量忽略不计。请问怎么选物品,价值最高?最高价值为多少? 输入 三行,前两行均有n个(3<=n<=2000)个1~100之间的整数,分别代表物品的整包重量、整包价格,第三行为整数m,为手推车载重。 输出 一个浮点数,保留2位,最高价值。 样例输入 Copy 8 8 20 12 5 9 10 40 46 60 49 26 45 30 25 样例输出 Copy 132.00
时间: 2024-04-15 16:27:31 浏览: 100
下面是根据您的要求编写的代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
struct Item {
int weight;
int price;
Item(int weight, int price) {
this->weight = weight;
this->price = price;
}
};
float calculateMaxValue(vector<Item>& items, int capacity) {
vector<float> dp(capacity + 1, 0);
for (int i = 1; i <= items.size(); i++) {
for (int j = capacity; j >= items[i - 1].weight; j--) {
dp[j] = max(dp[j], dp[j - items[i - 1].weight] + items[i - 1].price);
}
}
return dp[capacity];
}
int main() {
vector<int> weights;
vector<int> prices;
int capacity, weight, price;
// 读取整包重量
while (cin >> weight) {
weights.push_back(weight);
if (cin.get() == '\n') {
break;
}
}
// 读取整包价格
while (cin >> price) {
prices.push_back(price);
if (cin.get() == '\n') {
break;
}
}
cin >> capacity;
// 构建物品数组
vector<Item> items;
for (int i = 0; i < weights.size(); i++) {
items.push_back(Item(weights[i], prices[i]));
}
float maxValue = calculateMaxValue(items, capacity);
cout << fixed;
cout.precision(2);
cout << maxValue << endl;
return 0;
}
```
这段代码使用了动态规划的思想,通过构建一个二维数组 `dp` 来保存每个容量下的最大价值。在计算最大价值时,遍历物品并更新 `dp` 数组,最终返回 `dp[capacity]` 即为最高价值。注意,这里使用了浮点数来保存最大价值,并通过 `cout.precision(2)` 设置输出的小数点位数为 2。
希望这段代码能够满足您的需求!
阅读全文