再问个01背包问题（也是回溯法实现）

august

图中给出3件物品（n）, C是背包的容量，W，V就是1~n件物品的重量和价值。

相近的解题方法如下：

2. #include<iostream>
3. using namespace std;
5. class Knap
6. {
7.     friend int Knapsack(int p[],int w[],int c,int n);
8.     public:
9.            void print()
10.            {
11.                for(int m=1;m<=n;++m)
12.                    cout << bestx[m] << " ";
13.                cout << endl;
14.            }
15.            
16.     private:
17.             int Bound(int i);
18.             void Backtrack(int i);
19.             int c; //背包容量
20.             int n; //物品数
21.             int *w;//物品重量数组
22.             int *p;//物品价值数组
23.             int cw;//当前重量
24.             int cp;//当前价值
25.             int bestp;//当前最优值
26.             int *bestx;//当前最优解
27.             int *x;//当前解
28. };
30. int Knap::Bound(int i)
31. {
32.     //计算上界
33.     int cleft = c - cw;//剩余容量
34.     int b = cp;
35.    
36.     //以物品单位重量价值递减序装入物品
37.     while(i<=n && w[i]<=cleft)
38.     {
39.         cleft -= w[i];
40.         b += p[i];
41.         ++i;
42.     }
43.     //装满背包时
44.     if(i<=n) b += p[i]/w[i]*cleft;
45.     return b;
46. }
47. void Knap::Backtrack(int i)
48. {
49.     if(i>n)
50.     {
51.         if(bestp<cp)
52.         {
53.             for(int j=1;j<=n;++j)
54.                 bestx[j] = x[j];
55.             bestp = cp;
56.         }
57.         return;
58.     }
59.     if(cw+w[i]<=c) //搜索左子树
60.     {
61.         x[i] = 1;
62.         cw += w[i];
63.         cp += p[i];
64.         Backtrack(i+1);
65.         cw -= w[i];
66.         cp -= p[i];
67.     }
68.     if(Bound(i+1)>bestp) //搜索右子树
69.     {
70.         x[i] = 0;
71.         Backtrack(i+1);
72.     }
73. }
75. class Object
76. {
77.     friend int Knapsack(int p[],int w[],int c,int n);
78.     public:
79.            int operator<=(Object a) const
80.            {
81.                return (d>=a.d);
82.            }
83.     private:
84.             int ID;
85.             float d;
86. };
88. int Knapsack(int p[],int w[],int c,int n)
89. {
90.     int W = 0;
91.     int P = 0;
92.     int i = 1;
93.     Object *Q = new Object[n];
94.    
95.     for(i=1;i<=n;++i)
96.     {
97.         Q[i-1].ID = i;
98.         Q[i-1].d = 1.0*p[i]/w[i];
99.         P += p[i];
100.         W += w[i];
101.     }
102.     if(W<=c)
103.         return P; //装入所有物品
104.     //依物品单位重量排序
105.     float f;
106.     for(i=0;i<n;++i)
107.         for(int j=i;j<n;++j)
108.         {
109.            if(Q[i].d<Q[j].d)
110.            {
111.                f = Q[i].d;
112.                Q[i].d = Q[j].d;
113.                Q[j].d = f;
114.            }
115.         }
116.         
117.     Knap K;
118.     K.p = new int[n+1];
119.     K.w = new int[n+1];
120.     K.x = new int[n+1];
121.     K.bestx = new int[n+1];
122.     K.x[0] = 0;
123.     K.bestx[0] = 0;
124.     for(i=1;i<=n;++i)
125.     {
126.         K.p[i] = p[Q[i-1].ID];
127.         K.w[i] = w[Q[i-1].ID];
128.     }
129.     K.cp = 0;
130.     K.cw = 0;
131.     K.c = c;
132.     K.n = n;
133.     K.bestp = 0;
134.     //回溯搜索
135.     K.Backtrack(1);
136.     K.print();
137.     delete[] Q;
138.     delete[] K.w;
139.     delete[] K.p;
140.     return K.bestp;
141. }
143. int main(void)
144. {
145.     int *p;
146.     int *w;
147.     int c=0;
148.     int n=0;
149.     int i=0;
150.    
151.     cout << "请输入物品个数n：" << endl;
152.     cin >> n;
153.     p = new int[n+1];
154.     w = new int[n+1];
155.     p[0] = 0;
156.     w[0] = 0;
157.    
158.     cout << "请输入n个物品的价值:" << endl;
159.     for(i=1;i<=n;++i)
160.         cin >> p[i];
161.    
162.     cout << "请输入N个物品的重量：" << endl;
163.     for(i=1;i<=n;++i)
164.         cin >> w[i];
165.         
166.     cout << "请输入背包容量：" << endl;
167.         cin >> c;
168.         
169.     cout << Knapsack(p,w,c,n) << endl;
170.     system("PAUSE");
171.     return 0;
172. }

复制代码

还是比较多不懂的地方，像类里面的Bound方法最后那句://装满背包时
    if(i<=n) b += p/w*cleft;
第i物品的价值/第i物品的重量*背包剩余容量是什么意思？
在这个IF之前的循环不是已经把重量都得到了吗？

还有就是它到底是怎么分别左右子树的？ 晕晕的

Zelsazgh

这个算法的关键是把单个物品的价值最大的计算出来即p/w，然后放入到包中p/w*cleft，为确保有足够的空间，所以要IF一下，然后再放入包中,b += p/w*cleft;

august

还是不明白,单个物品的价值最大的计算出来? p不就是这物品的价值了吗？

Zelsazgh

p是总体价值,不是单数价值

august

C++还只是学了点皮毛，这程序看得很吃力。于是把它转成C语言描述了。

2. #include&lt;stdio.h&gt;
3. #include&lt;stdlib.h&gt;
5. int content;        //背包容量
6. int n;              //物品数
7. int *weight;        //存放n个物品重量的数组
8. int *price;         //存放n个物品价值的数组
9. int currentWeight;  //当前重量
10. int currentPrice;   //当前价值
11. int bestPrice;      //当前最优值
12. int *bestAnswer;    //当前最优解
13. int *cAnswer;       //当前解
15. int Bound(int i) //检验子树是否能产生合适解的函数
16. {
17.     int cleft = content - currentWeight; //求背包剩余容量
18.     int p = currentPrice; //当前背包所装物品价值
19.    
20.     while(i&lt;=n &amp;&amp; weight[i]&lt;=cleft)
21.     {
22.         cleft -= weight[i];
23.         p += price[i];
24.         ++i;
25.     }
26.     return p; //返回价值p
27. }
28. void Backtracking(int i)
29. {
30.     int j;
31.     if(i&gt;n)
32.     {
33.         if(bestPrice&lt;currentPrice) //最优值小于当前价值则赋值
34.         {
35.             for(j=1;j&lt;=n;++j)
36.                 bestAnswer[j] = cAnswer[j]; //取得树上路径
37.             bestPrice = currentPrice;
38.         }
39.         return;
40.     }
41.     if(currentWeight+weight[i]&lt;=content)//当前重量+该物品重量 &lt;= 背包容量
42.     {
43.         //搜索左子树
44.         cAnswer[i] = 1;
45.         currentWeight += weight[i];
46.         currentPrice += price[i];
47.         Backtracking(i+1);
48.         //完成上面的递归，返回到上一结点，准备递归右子树
49.         currentWeight -= weight[i];
50.         currentPrice -= price[i];
51.     }
52.     if(Bound(i+1)&gt;bestPrice) //搜索右子树，如返回值大于当前最优值，则执行
53.     {
54.          cAnswer[i] = 0;
55.          Backtracking(i+1);
56.     }
57. }
58. void Print()
59. {
60.     int i;
61.    
62.     printf(&quot;\\n\\nthe bestAnswer={&quot;);
63.     for(i=1;i&lt;n;++i)
64.         printf(&quot;%d,&quot;,bestAnswer[i]);
65.     printf(&quot;%d}\\tthe bestPrice=%d\\n&quot;,bestAnswer[i],bestPrice);
66. }
67. void Destroy() //销毁分配空间
68. {
69.     free(price);
70.     free(weight);
71.     free(bestAnswer);
72.     free(cAnswer);
73. }
74. int main(void)
75. {
76.     int i;
77.     //输入物品数量
78.     printf(&quot;please enter article amount:\\n&quot;);
79.     scanf(&quot;%d&quot;,&amp;n);
80.     //输入物品价格
81.     printf(&quot;please enter all articles price:\\n&quot;);
82.     if(!(price=(int*)malloc((n+1)*sizeof(int)))) exit(1);
83.     for(i=1;i&lt;=n;++i)
84.         scanf(&quot;%d&quot;,&amp;price[i]);
85.     //输入物品重量
86.     printf(&quot;please enter all articles weight:\\n&quot;);
87.     if(!(weight=(int*)malloc((n+1)*sizeof(int)))) exit(1);
88.     for(i=1;i&lt;=n;++i)
89.         scanf(&quot;%d&quot;,&amp;weight[i]);
90.     //输入背包容量   
91.     printf(&quot;please enter knapsack&#39;s content:\\n&quot;);
92.     scanf(&quot;%d&quot;,&amp;content);
93.    
94.     if(!(bestAnswer=(int*)malloc((n+1)*sizeof(int)))) exit(1);
95.     if(!(cAnswer=(int*)malloc((n+1)*sizeof(int)))) exit(1);
96.    
97.     Backtracking(1);//回溯法搜索最优解
98.     Print(); //打印结果
99.   Destroy();
100.    
101.     system(&quot;PAUSE&quot;);
102.     return 0;
103. }

复制代码