问题描述

假设山洞中有n种宝物,每种宝物都有一定重量w和相应的价值v,老驴运载能力有限,只能运走m重量的宝物,一种宝物只能拿一样,宝物可以分割,那么怎么才能使毛驴运走宝物的价值最大?

解题策略

策略1:根据物品的重量从小到大排序,依次选择物品进入背包,使得剩余质量消耗慢

策略2:根据物品的价值从大到小排序,优先选择价值大的物品进入背包,使得总价值达到最大

策略3:根据物品的价值与质量的比,即效益比,按照效益比的从大到小优先选入背包

通过列举反例,我们可以推翻策略1,2, 策略3就是我们可以利用求得最优解的策略

  1. 初始化数据(注意记录物品的原始序号,因为按照效益比排列之后,物品的顺序会打乱,最终虽然效益一样,但是物品的编号会不同)
  2. 对物品的效益比进行排序
  3. 按照质量剩余多少选择物品
  4. 输出效益

代码

实例:背包的承重M=20,物品的个数n=3,质量分别为18,15,10。相对应的价值分别为25,24,15

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdio.h>

//定义装入背包的物品
typedef struct {
double v, m; //物品的价值,质量
double vm; //物品的效益质量比
int id; //物品的编号
} Goods;

Goods goods[1000]; //物品集合
double numberGoods[1000]; //物品的份额对应的向量解

void swap(Goods goods[], int index1, int index2)
{
Goods tempGoods = goods[index1];
goods[index1] = goods[index2];
goods[index2] = tempGoods;
}

int partition(Goods goods[], int low, int high)
{
Goods pivot = goods[low];
while(low < high){
while((low < high) && (pivot.vm <= goods[high].vm))
high--;
swap(goods, low, high);
while((low < high) && (pivot.vm >= goods[low].vm))
low++;
swap(goods, low, high);
}
return low;
}

void quickSort(Goods goods[], int low, int high)
{
if (low < high) {
int part = partition(goods, low, high);
quickSort(goods, low, part-1);
quickSort(goods, part+1, high);
}
}

void main()
{
double M;
printf("请输入背包的承重:");
scanf("%lf", &M);

int n;
printf("请输入物品的数量:");
scanf("%d", &n);

for(int i = 1; i <= n; i++)
{
printf("请输入物品%d的重量和价值:", i);
scanf("%lf %lf", &goods[i].m, &goods[i].v);
goods[i].vm = goods[i].v / goods[i].m;
goods[i].id = i; //记录编号
}

quickSort(goods, 1, n);
// for(int i = 1; i <= n; i++)
// printf("%lf\t", goods[i].vm);

int cm = M; //记录背包当前剩余承重
double cv = 0; //记录背包当前价值
for(int i = n; i >= 1 && cm > 0; i--)
{
if(cm > goods[i].m)
{
numberGoods[i] = 1;
cm -= goods[i].m;
cv += goods[i].v;
}
else{
numberGoods[i] = (cm / goods[i].m);
cv += numberGoods[i] * goods[i].v;
cm = 0;
}
}

for(int i = 1; i <= n; i++)
{
if (numberGoods[i] != 0) {
printf("物品%d的份额为:%lf\n", goods[i].id, numberGoods[i]);
}
}
}