物品可以被分割，具体问题不再赘述。
由于此问题具有最优子结构性质（问题的最优解包含其子问题的最优解），所以适合使用贪心策略。
依据贪心策略，将尽可能多的单位重量价值最高的物品装入背包。
写的不好，请不要吐槽代码冗余，看明白了，理解了这道题就行了。
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;
}