回溯法求解0/1背包问题

给定背包的载重量M＝20，有6个物体，价值分别为11，8，15，18，12，6，重量分别为5，3，2，10，4，2。利用回溯法求解上述问题。

一、 算法思想描述

对每个结点考虑两种情况——放入和没放入，每个分支开始时计算该分支可能达到的最大上界，如果小于当前已经能达到的上界，则不继续计算该分支，否则深入计算，直到找到最优解为止。

二、 完整的程序以及说明

Code:

1. #include<iostream>   
2. #include<algorithm>   
3. using namespace std;   
4.     
5. //      物体结构体   
6. typedef struct{   
7.         float w;   
8.         float p;   
9.         float v;   
10.         int id;   
11. }OBJECT;   
12.     
13. bool cmp(OBJECT a, OBJECT b){   
14.         return a.v>b.v;   
15. }   
16.     
17. float knapsack_back(OBJECT ob[], float M, int n, bool x[]){   
18.         int i,k;   
19.         float w_cur, p_total, p_cur, w_est, p_est;   
20.         bool *y = new bool[n+1];   
21.     
22.         //      计算物体的价值重量比   
23.         for(i=0; i<=n; i++){   
24.                 ob[i].v = ob[i].p/ob[i].w;   
25.                 y[i] = false;   
26.         }   
27.     
28.         //      按照物体的价值重量比降序排列   
29.         sort(ob, ob+n, cmp);   
30.     
31.         //      初始化当前背包中的价值、重量   
32.         w_cur = p_cur = p_total = 0;   
33.     
34.         //      已搜索的可能解的总价值初始化   
35.         k = 0;   
36.         while(k>=0){   
37.                 w_est = w_cur; p_est = p_cur;   
38.     
39.                 //      沿当前分支可能取得的最大价值   
40.                 for( i=k; i<n; i++) {   
41.                         w_est += ob[i].w;   
42.                         if(w_est<M){   
43.                                 p_est += ob[i].p;   
44.                         }else{   
45.                                 p_est += ((M-w_est+ob[i].w)/ob[i].w)*ob[i].p;   
46.                                 break;   
47.                         }   
48.                 }   
49.     
50.                 //      估计值大于上界   
51.                 if(p_est>p_total){   
52.                         for(i=k; i<n; i++){   
53.                                 if(w_cur+ob[i].w<=M){   
54.                                         //      可装入第i个物体   
55.                                         w_cur = w_cur + ob[i].w;   
56.                                         p_cur = p_cur + ob[i].p;   
57.                                         y[i] = true;   
58.                                 }else{   
59.                                         //      不能装入第i个物体   
60.                                         y[i] = false;   
61.                                         break;   
62.                                 }   
63.                         }   
64.                         if(i>=n){   
65.                                 //      n个物体已经全部装入   
66.                                 if(p_cur>p_total){   
67.                                         //      更新当前上限   
68.                                         p_total = p_cur;   
69.                                         k = n;   
70.                                         //      保存可能的解   
71.                                         for(i=0; i<n; i++){   
72.                                                 x[i] = y[i];   
73.                                         }   
74.                                 }   
75.                         }else{   
76.                                 //      继续装入物体   
77.                                 k = i+1;   
78.                         }   
79.                 }else{   
80.                         //      估计值小于上界时   
81.                         while((i>=0)&&(!y[i]))i--;      //    沿着右分支结点方向回溯直到左分支结点   
82.                         if(i<0)break;            // 到达根结点 算法结束   
83.                         else{                  // 修改当前值   
84.                                 w_cur -= ob[i].w;   
85.                                 p_cur -= ob[i].p;   
86.                                 y[i] = false;   
87.                                 k = i+1;                                //      搜索右分支子树   
88.                         }   
89.                 }   
90.         }   
91.         //delete y;   
92.         return p_total;   
93. }   
94.     
95. int main(){   
96.         int n;   
97.         float m;   
98.     
99.         cout<<"请输入背包载重：";   
100.         cin>>m;   
101.     
102.         cout<<"请输入物品个数：";   
103.         cin>>n;   
104.     
105.         OBJECT* ob = new OBJECT[n];   
106.         {   
107.                 cout<<"请输入物品的重量、价格："<<endl;   
108.                 for(int i=0; i<n; i++){   
109.                         cin>>ob[i].w>>ob[i].p;   
110.                         ob[i].id = i+1;   
111.                 }   
112.         }   
113.     
114.         bool* x = new bool[n];   
115.     
116.         float v = knapsack_back(ob, m, n, x);   
117.     
118.         {   
119.                 cout<<"最优方案："<<endl;   
120.                 for(int i=0; i<n; i++){   
121.                         if(x[i])cout<<"["<<ob[i].id<<"] ";   
122.                 }   
123.                 cout<<endl;   
124.                 cout<<"物品总价值为："<<v<<endl;   
125.         }   
126.     
127.         return 0;   
128. }