物品可以被分割,具体问题不再赘述。
由于此问题具有最优子结构性质(问题的最优解包含其子问题的最优解),所以适合使用贪心策略。
依据贪心策略,将尽可能多的单位重量价值最高的物品装入背包。
写的不好,请不要吐槽代码冗余,看明白了,理解了这道题就行了。
C++ 代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// 物品
struct Goods
{
int weight; // 物品重量
int value; // 物品价值
double price_quality_ratio; // 物品单位重量的价值

Goods(int w, int v) :weight(w), \
value(v), price_quality_ratio(v / w) {}

// 根据价值重量比由大到小排序
bool operator<(Goods g)
{
return this->price_quality_ratio > g.price_quality_ratio;
}
};

// 背包
struct Bag
{
int capacity; // 背包容量
vector<Goods> set; // 背包放入的物品集合
vector<double> put_in_ratio; // 物品放入的比例

Bag(int c) :capacity(c) {}
};

// 获取物品装满背包时最大的价值
void GetMaxValueBag(vector<Goods> &set, Bag &g)
{
// 根据价值重量比将物品集由大到小排序
sort(set.begin(), set.end());

// 当前背包剩余容量
int current_capacity = g.capacity;

// 从第一个物品开始
int index = 0;
while (index < set.size())
{

if (current_capacity >= set[index].weight)
{
// 将当前的物品装入背包
current_capacity -= set[index].weight;
g.set.push_back(set[index]);
g.put_in_ratio.push_back(1);
index++;
}
else
{
// 根据剩余空间的比例放入物品并结束
g.set.push_back(set[index]);
g.put_in_ratio.push_back(double(current_capacity) / set[index].weight);
break;
}
}
}

测试用如下:
背包容量 50
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
Bag bag(50);
vector<Goods> goodsSet = { Goods(20,60), Goods(30,120), Goods(10,50) };

GetMaxValueBag(goodsSet, bag);

double total_value = 0.0;
for (int i = 0;i<bag.set.size();++i)
{
cout << "物品重量:" << bag.set[i].weight << ",物品价值:"
<< bag.set[i].value << ",物品装入比例:" << bag.put_in_ratio[i] << endl;
total_value += bag.set[i].value*bag.put_in_ratio[i];
}
cout << "装入背包物品总价值为:" << total_value << endl;
}