1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct {
	float		w;			/* 物体重量 */
	float		p;			/* 物体价值 */
	float		v;			/* 物体的价值重量比 */
} OBJECT;

OBJECT	ob[n];			
float		M;				/* 背包载重量 */
int		x[n];			/* 可能的解向量 */
int		y[n];			/* 当前搜索的解向量 */
float		p_est;			/* 当前搜索方向装入背包物体的估计最大价值 */
float		p_total;		/* 装入背包的物体的最大价值的上界 */
float		w_cur;			/* 当前装入背包的物体的总重量 */
float		p_cur;			/* 当前装入背包的物体的总价值 */

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
 1. float knapsack_back(OBJECT ob[],float M,int n,BOOL x[])
 2. {
 3.     int i,k;
 4.     float w_cur,p_total,p_cur,w_est,p_est;
 5.     BOOL *y = new BOOL[n]; 
 6.     for (i=0;i<=n;i++) {				/* 计算物体的价值重量比 */
 7.         ob[i].v = ob[i].p / ob[i].w;
 8.         y[i] = FALSE;					/* 当前的解向量初始化 */
 9.     }
10.     merge_sort(ob,n);					/* 物体按价值重量比的非增顺序排序*/
11.     w_cur = p_cur = p_total = 0;		/* 当前背包中物体的价值重量初始化*/
12.     k = 0;								/* 已搜索到的可能解的总价值初始化*/
13.     while (k>=0) {
14.         w_est = w_cur;   p_est = p_cur;
15.         for (i=k;i<n;i++) {			/* 沿当前分支可能取得的最大价值 */
16.             w_est = w_est + ob[i].w;
17.             if (w_est<M) {
18.                 p_est = p_est + ob[i].p;
19.             else {
20.                 p_est = p_est + ((M – w_est + ob[i].w) / ob[i].w) * ob[i].p;
21.                 break;
22.             }
23.         }
24.         if (p_est>p_total) {					/* 估计值大于上界 */
25.             for (i=k;i<n;i++) {
26.                 if (w_cur+ob[i].w<=M) {			/* 可装入第i个物体 */
27.                     w_cur = w_cur + ob[i].w; 
28.                     p_cur = p_cur + ob[i].p;
29.                     y[i] = TRUE;  
30.                 } 
31.                 else {
32.                     y[i] = FALSE;   break;		/* 不能装入第i个物体 */
33.                 }
34.             }
35.             if (i>=n) {							/* n个物体已全部装入 */
36.                 if (p_cur>p_total) {
37.                     p_total = p_cur;   k = n;	/* 刷新当前上限 */
38.                     for (i=0;i<n;i++) 			/* 保存可能的解 */
39.                         x[i] = y[i];			
40.                 }    
41.             }
42.             else k = i + 1;					/* 继续装入其余物体 */
43.         }
44.         else {								/* 估计价值小于当前上限*/
45.             while ((i>=0)&&(y[i]==0)		/* 沿着右分支结点方向回溯*/
46.                 i = i – 1;					/* 直到左分支结点 */
47.             if (i<0) break;					/* 已到达根结点,算法结束 */
48.             else {
49.                 w_cur = w_cur – ob[i].w;		/* 修改当前值 */	
50.                 p_cur = p_cur – ob[i].p;
51.                 y[i] = FALSE;   k = i + 1;	/* 搜索右分支子树 */
52.             }
53.         }
54.     }
55.     delete y;
56.     return p_total;
57. }