AlgorithmCodes/A05.01.cpp at master · tzayuan/AlgorithmCodes · GitHub

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
89
90
91
92
93
94
95
96
97
//Algorithm 5.1 (P143-4)(A05.01.cpp)
//可分割背包(knapsack)问题的贪婪算法
#include "headers.h"
class ClsKnapsackObj
{
public:
	int volume;  //体积
	int value; //价值
	double vaRatio; //单位体积的价值
	ClsKnapsackObj(){}
	void set(int vo, int va)
	{
		volume = vo;
		value = va;
		vaRatio = (double)va / vo;
	}
	bool operator < (ClsKnapsackObj &right)
	{
		return vaRatio < right.vaRatio;
	}
};
double knapsackGreedy(ClsKnapsackObj objs[],int n,
	int tVo, double voArr[])
{
	double tva = 0;
	int tvo = tVo;
	for (int i=n-1; i>=0; i--) {
		if (objs[i].volume <= tvo) {
			voArr[i] = 1;
			tvo -= objs[i].volume;
			tva += objs[i].value;
		}
		else {
			voArr[i] = (double)tvo / objs[i].volume;
			tva += tvo * objs[i].vaRatio;
			break;
		}
	}
	return tva;
}
int initKnapsackObjs(ClsKnapsackObj *objs, int n)
{
	int V=0;
	for (int i=0; i<n; i++) {
		objs[i].set(randRange(1,20), randRange(1,20));
		V += objs[i].volume;
	}
	return V;
}
void printKnapsackData(ClsKnapsackObj *objs, int n)
{
	printf("Obj No");
	for (int i=0; i<n; i++)
		printf("%6d", i+1);
	printf("\n");
	printf("Volume");
	for (int i=0; i<n; i++)
		printf("%6d", objs[i].volume);
	printf("\n");
	printf("Value ");
	for (int i=0; i<n; i++)
		printf("%6d", objs[i].value);
	printf("\n");
	printf("Ratio ");
	for (int i=0; i<n; i++)
		printf("%6.2lf", objs[i].vaRatio);
	printf("\n");
}
void knapsackGreedyTest(int n)
{
	printf("测试可分割背包(knapsack)问题的贪婪算法...\n");
	ClsKnapsackObj *objs = new ClsKnapsackObj[n];
	int Vt = initKnapsackObjs(objs, n);
	printf("原始物品：\n");
	printKnapsackData(objs, n);
	mergeSortRT <ClsKnapsackObj> (objs,0,n-1);
	printf("按单位价值排序：\n");
	printKnapsackData(objs, n);
	int V = randRange(Vt/3, Vt);
	double *voArr = new double[n];
	for (int i=0; i<n; i++)
		voArr[i] = 0;
	double Va = knapsackGreedy(objs, n, V, voArr);
	printf("体积为%d的背包最多可装下价值为%5.2lf的物品，\n",
		V, Va);
	printf("具体情况为：\n");
	printf("Vols  ");
	for (int i=0; i<n; i++)
		printf("%6.2lf", voArr[i]*objs[i].volume);
	printf("\n");
	printf("Values");
	for (int i=0; i<n; i++)
		printf("%6.2lf", voArr[i]*objs[i].volume*objs[i].vaRatio);
	printf("\n");
	delete objs;
	delete voArr;
}