01背包问题蛮力算法求解
1、根据物品个数n，我们都知道每一个物品都有放与不放两种情况，那么就有2的n次方中情况，那么我们就一种一种情况进行比较，那么首先我们要做一个b[n]的数组，这个数组每次都要根据情况算法算出一种情况保存在b[n]数组中，得到情况数组后，我们进行装背包和价格累加运算，最后算出来后看这种情况装的物品重量是否大于背包的总重量，如果大于则不符合，直接淘汰，如果小于等于背包的总重量，那么进行与之前可以装背包的物品价值进行比较，如果当前情况的价值小于之前的价值，直接淘汰，如果当前情况的价值大于之前的价值，保存此刻的价值，并把情况数组赋值给最终情况数组，作为装包的物品记录。那么最后输出总价值，和装入的物品就是根据计算后的总价值和最终的情况数组。这是我对蛮力算法求解这个问题的理解。
2、剖析代码1
2
3
4
5
6
7
8
9
10
11void conversion(int n,int b[MAX])
{
int i;
for(i=0;i<MAX;i++)
{
b[i] = n%2;
n = n/2;
if(n==0)
break;
}
}
这段代码很经典，符合场景为:比如你每一个事件都有放与不放，走与不走两种情况，那么你有m个事件，你就有pow(2,m)中情况，那么要怎么列举出来呢，难道要11,00,10,01写出来吗？肯定不会。那么这个方法，就是你把是第n种情况的n传进去，那么他就会给你计算出一个一维数组，那么这个一维数组就是你m个事件中的一种情况。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
54void force(){
int i,j,c,b[MAX],temp[MAX];
int tw,maxv,v[MAX],temp_w,temp_v;
printf("\t\t\t输入物品个数 n:");
scanf("%d",&n); //n为个数
printf("\n");
printf("\t\t\t输入背包重量 c:");
scanf("%d",&tw); //tw为重量
printf("\n");
for(i=0;i<n;i++)
{
printf("\t\t\t输入第 %d 个物品的重量,价格",i+1);
printf("\n\t\t\t");
scanf("%d,%d",&w[i],&v[i]); //w数组为重量，v为价格
}
maxv = 0;
for (i=0;i<pow(2,n);i++)
{
for (j=0;j<n;j++)
{
b[j] = 0;
}
conversion(i,b);
temp_v = 0;
temp_w = 0;
for (j=0;j<n;j++)
{
if (b[j]==1)
{
temp_w = temp_w+w[j];
temp_v = temp_v + v[j];
}
}
if ((temp_w <= tw)&&(temp_v>maxv))
{
for (j=0;j<n;j++)
{
temp[j] = 0;
}
maxv = temp_v;
for (j=0;j<n;j++)
{
temp[j] = b[j];
}
}
}
printf("\t\t\t此背包能装的最大价值:%d\n",maxv);
printf("\t\t\t选择的物品有:\n");
for (j=0;j<n;j++)
{
if(temp[j])
printf("\t\t\t第%d个物品，重量 为%d，价值为%d\n", j+1,w[j],v[j]);
}
}
然后把每一种情况都算一遍，看在满足背包容量的情况下是否有最大价值，这里面隐含了一个冒泡排序，只是有点分散了，不太明显，但还是有的。最后maxv，temp放的是最大价值和最终放的物品，temp一维数组中，标识位为1对应的下表值就是第几个物品已装入。
01背包问题递归算法求解
1、01背包问题，是当背包装入物品的重量不得大于背包的容量，所以递归的边界分为两种，一种就是装入的物品重量大于背包的容量则返回，当装完当前的物品则返回。分为两种递归，一种是放入此物品递归，另一种是不放入此物品递归，而且当递归返回的时候要判断两种装入和不装入递归返回的大小，那么当返回装入此物品的时候，就要加上这个物品的价值。在装入这个物品时候，设置一个标识位，表示这个物品装入了。最终按照这个标志位来输出放入的物品。
2、剖析代码1
2
3
4
5
6
7
8
9
10
11
12
13int Make(int i,int j){
int res;
if(i==-1){
return 0;
}
else if(j>=w[i]&&Make(i-1,j)<Make(i-1,j-w[i])+p[i]){
x[i]=1;
return Make(i-1,j-w[i])+p[i];
}else{
x[i]=0;
return Make(i-1,j);
}
}
为什么是i==-1，因为我用一维数组存的物品和重量，那么最终装完，要不是到下标值为4或者为0，所以如果采用从0开始，结束的应该是i==5，如果采用从4开始，结束的应该是i==-1，都可以用。第二个else if是第二个结束条件，每次都要判断当前背包的重量是否能装入这个物品，如果能还要判断当装入了这个物品和没装入这个物品两者的价值比较，如果装入的价值大于没装入的肯定要装进去咯。这里可能你们会有点疑问，装入后肯定价值要大一些呀，其实这里的装入，是最终的装入，这里有点不好说清楚，就是你已经递归完成后，其实所有的情况的总价值都算出来，倒过来在看装入这个物品的总价值和没装入这个物品的总价值进行对比。就是说向下的递归条件还有加入这个物品的总价值进行比较，来决定他放不放。
传入的就是物品个数和背包重量，因为这两个是结束条件，而另一个隐含的结束条件就是总价值大小。
01背包问题动态规划算法求解
动态规划建立递推关系，建立二维数组，二维数组的行容量为物品的重量加1，而列容量为物品的个数。那么在第一个物品装包的时候我们向二维数组的第一行写入在背包总容量之下的每一个容量所能装入的物品产生的价值。第一个装入的物品可以作为初始化递推条件。在进行下面物品递推的过程中，我们以上一行作为基础，进行递推。那么在进行下一行的最大价值结算要结合上一行的价值的大小进行比较或者相加。得出此时的最大价值。以此类推最终形成整个二维表。然后从二维表的最右端的最下面与它的上一行进行比较如果他大于上一行就进行装包，如果不大于则往上移进行比较，若他大于他的上一行就装包。最终计算出装包的所有物品。
这个我认为是最有思想的了，这个要把模型建立起来，如果没有模型不好想，因为我一开始一直在一维空间里面想，就算开始进入了二维空间，一会又乱了，可能我画图会画顺推的图，代码写逆推的。
就拿背包容量为10，第一个物品重量2,6第二个2,3，第三个6,5，第四个5,4，第五个4，6.
| 物品重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 2,6 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
| 2,3 | 0 | 0 | 6 | 6 | 9 | 9 | 9 | 9 | 9 | 9 | 9 |
| 6,5 | 0 | 0 | 6 | 6 | 9 | 9 | 9 | 9 | 11 | 11 | 14 |
| 5,4 | 0 | 0 | 6 | 6 | 9 | 9 | 9 | 10 | 11 | 13 | 14 |
| 4,6 | 0 | 0 | 6 | 6 | 9 | 9 | 12 | 12 | 15 | 15 | 15 |
这就是整个分析图。
我来说说怎么分析的吧！
首先二维数组的横下标表示当前背包当前的容量，那么在当前容量下到底能放什么呢？就要根据这个二维表来算，怎么算呢？
我按行来分析吧！我们要先初始化一个物品作为二维表的第一行，随便拿一个，比如说我第一行放的是2,6这个物品，那么当背包容量为0时放不下，价值就为零，1时放不下价值为0,2时放得下了那么价值就变为6了是不是。也就是说你给我背包容量大于2的我都能放得下这个物品，价值为6.
这时候来了第二个物品，我们还是先按照第一个物品来算，背包容量为0时，放不下，最大价值为0,1时还是放不下，2时可以放下了，但是你要考虑最大价值，现在有两个物品，并且背包容量只有2,那么这时候的步骤应该是这样的你要用此刻的背包容量减去你当前要装的物品剩下的容量对应的价值是多少，然后加上当前物品的价值，然后再与上面的背包容量为2所装的东西进行比较，发现之前的背包容量为2的价值比你现在还要大，所以你这个没必要装。
以此类推，最终得到这个二维表，发现最终得到的最大价值为15。
到这还没结束，你还要把装进去的物品推出来。先比较最后一个物品是否装进去了，如果最后一行的最后一列大于倒数第二行的最后一列说明已经装进去了，如果没有那么找倒数第二行的最大值与上一个比较，找到之后用10减去4得到6，那么找到上一行的第六列再与上一行的第六列进行比较，如果相等再往上一行比较，知道找到变化的一行，以次类推找出所有装入背包的物品。
下面给出逆推算法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
39void dynamic(){
int i,j,cw,c,sw,sp,a[MAX],b[MAX],g[MAX][10*MAX];
printf("\t\t\t输入物品个数 n:");
scanf("%d",&n);
printf("\t\t\t输入背包重量 c:");
scanf("%d",&c);
for(i=1;i<=n;i++){
printf("\t\t\t输入第 %d个物品的重量,价值:",i);
printf("\n\t\t\t");
scanf("%d,%d",&b[i],&a[i]);
}
for(j=0;j<=c;j++)
if(j>=b[1])
g[1][j]=a[1];
else
g[1][j]=0;
for (i = 2; i <=n; i++)
for (j = 0; j <= c; j++)
if(j>=b[i]&&g[i-1][j]<g[i-1][j-b[i]]+a[i])
g[i][j]=g[i-1][j-b[i]]+a[i];
else
g[i][j]=g[i-1][j];
cw=c;
printf("\t\t\tc=%d\n",c );
printf("\t\t\t选择的物品有:\n");
for(sp=0,sw=0,i=n;i>=2;i--)
if(g[i][cw]>g[i-1][cw]){
cw-=b[i];
sw+=b[i];
sp+=a[i];
printf("\t\t\t第%2d个物品，重量为 %3d 价格为%3d\n",i,b[i],a[i]);
}
if(g[n][c]-sp==a[i]){
sw+=b[i];
sp+=a[i];
printf("\t\t\t第%2d个物品，重量为%3d 价格为 %3d\n",1,b[1],a[1] );
}
printf("\t\t\t重量=%d , 价格=%d\n",sw,sp );
}
这个就是实现01背包的三种算法。
总结:
蛮力算法，我认为就是把所有的情况都列出来，在列出情况之前没有限制条件，然后再根据每种情况，做实际的运算，然后根据限制条件判断此种情况是否符合当前问题的解决方案。
递归算法，我认为递归算法首先要找出递归的边界作为你递归的终结条件，而且这个条件的变量要作为递归式的形参，因为在往下传的时候肯定要改变这个条件，那么唯一能够动态改变值并且能够作为条件的就是形参。所以我们要把关于递归条件的放入形参。然后再设计递归式。
动态规划算法：这个我认为是最能理解的算法，根据背包容量和物品个数建立模型，然后根据模型进行推论，然后再根据推论设计算法。最终解决问题。
关于时间复杂度和空间复杂度，根据运行的时间结果，蛮力是最消耗时间的，而动态规划是时间消耗最短的。而至于递归，我感觉他利用了栈先进后出，消耗的空间要大一些。
另外，根据这些算法，我感觉解决一个问题最难的就是推导，比如说动态规划一开始就要给这个问题，建立模型，那么在抉择哪个模型适合是很困难的。
附录:完整代码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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
LARGE_INTEGER nFreq; //传出参数
LARGE_INTEGER nBeginTime; //传出起始时间
LARGE_INTEGER nEndTime; //传出结束时间
static int p[MAX]={0},w[MAX]={0},x[MAX]={0};
int n;
int Make(int i,int j){
int res;
if(i==-1){
return 0;
}
else if(j>=w[i]&&Make(i-1,j)<Make(i-1,j-w[i])+p[i]){
x[i]=1;
return Make(i-1,j-w[i])+p[i];
}else{
x[i]=0;
return Make(i-1,j);
}
}
void conversion(int n,int b[MAX])
{
int i;
for(i=0;i<MAX;i++)
{
b[i] = n%2;
n = n/2;
if(n==0)
break;
}
}
int getNum(int i){
srand((unsigned)time(NULL));
int number=rand()%(i+1);
return number;
}
void force(){
int i,j,c,b[MAX],temp[MAX];
int tw,maxv,v[MAX],temp_w,temp_v;
printf("\t\t\t输入物品个数 n:");
scanf("%d",&n); //n为个数
printf("\n");
printf("\t\t\t输入背包重量 c:");
scanf("%d",&tw); //tw为重量
printf("\n");
for(i=0;i<n;i++)
{
printf("\t\t\t输入第 %d 个物品的重量,价格",i+1);
printf("\n\t\t\t");
scanf("%d,%d",&w[i],&v[i]); //w数组为重量，v为价格
}
maxv = 0;
for (i=0;i<pow(2,n);i++)
{
for (j=0;j<n;j++)
{
b[j] = 0;
}
conversion(i,b);
temp_v = 0;
temp_w = 0;
for (j=0;j<n;j++)
{
if (b[j]==1)
{
temp_w = temp_w+w[j];
temp_v = temp_v + v[j];
}
}
if ((temp_w <= tw)&&(temp_v>maxv))
{
for (j=0;j<n;j++)
{
temp[j] = 0;
}
maxv = temp_v;
for (j=0;j<n;j++)
{
temp[j] = b[j];
}
}
}
printf("\t\t\t此背包能装的最大价值:%d\n",maxv);
printf("\t\t\t选择的物品有:\n");
for (j=0;j<n;j++)
{
if(temp[j])
printf("\t\t\t第%d个物品，重量 为%d，价值为%d\n", j+1,w[j],v[j]);
}
}
void recursive(){
int i,j,c,cw,sw,sp;
printf("\t\t\t输入物品的个数 n:");
scanf("%d",&n);
printf("\t\t\t输入背包的重量 c:");
scanf("%d",&c);
for(i=0;i<n;i++){
printf("\t\t\t输入第%d个物品的重量，价格",i+1 );
printf("\n\t\t\t");
scanf("%d,%d",&w[i],&p[i]);
}
int maxNum=Make(n-1,c);
printf("\t\t\t此背包能装的最大价值:%d\n",maxNum);
printf("\t\t\t选择的物品有:\n");
for(i=0;i<n;i++){
if(x[i]==1){
printf("\t\t\t第%d个物品，重量为%d,价格为%d\n",i+1,w[i],p[i]);
}
}
}
void dynamic(){
int i,j,cw,c,sw,sp,a[MAX],b[MAX],g[MAX][10*MAX];
printf("\t\t\t输入物品个数 n:");
scanf("%d",&n);
printf("\t\t\t输入背包重量 c:");
scanf("%d",&c);
for(i=1;i<=n;i++){
printf("\t\t\t输入第 %d个物品的重量,价值:",i);
printf("\n\t\t\t");
scanf("%d,%d",&b[i],&a[i]);
}
for(j=0;j<=c;j++)
if(j>=b[1])
g[1][j]=a[1];
else
g[1][j]=0;
for (i = 2; i <=n; i++)
for (j = 0; j <= c; j++)
if(j>=b[i]&&g[i-1][j]<g[i-1][j-b[i]]+a[i])
g[i][j]=g[i-1][j-b[i]]+a[i];
else
g[i][j]=g[i-1][j];
cw=c;
printf("\t\t\tc=%d\n",c );
printf("\t\t\t选择的物品有:\n");
for(sp=0,sw=0,i=n;i>=2;i--)
if(g[i][cw]>g[i-1][cw]){
cw-=b[i];
sw+=b[i];
sp+=a[i];
printf("\t\t\t第%2d个物品，重量为 %3d 价格为%3d\n",i,b[i],a[i]);
}
if(g[n][c]-sp==a[i]){
sw+=b[i];
sp+=a[i];
printf("\t\t\t第%2d个物品，重量为%3d 价格为 %3d\n",1,b[1],a[1] );
}
printf("\t\t\t重量=%d , 价格=%d\n",sw,sp );
}
void compareTime(){
QueryPerformanceFrequency(&nFreq); //传出精度
double cost1_time=0.0,cost2_time=0.0,cost3_time=0.0;
int i,j,k,tw;
int b[MAX],temp[MAX];
int temp_w,temp_v,maxv;
int g[MAX][10*MAX];
int cw;
printf("|-------------------------------------------------------------------------|\n");
printf("\t|物品个数|背包重量|蛮力算法\t|递归算法\t|动态规划算法|\n");
for(n=5;n<=100;n+=5){
for(tw=20;tw<=400;tw+=20){
for(k=0;k<n;k++){
p[k]=getNum(tw/2);
w[k]=getNum(tw/2);
}
QueryPerformanceCounter(&nBeginTime); //开始数据
maxv=0;
for (i=0;i<pow(2,n);i++)
{
for (j=0;j<n;j++)
{
b[j] = 0;
}
conversion(i,b);
temp_v = 0;
temp_w = 0;
for (j=0;j<n;j++)
{
if (b[j]==1)
{
temp_w = temp_w+w[j];
temp_v = temp_v + p[j];
}
}
if ((temp_w <= tw)&&(temp_v>maxv))
{
for (j=0;j<n;j++)
{
temp[j] = 0;
}
maxv = temp_v;
for (j=0;j<n;j++)
{
temp[j] = b[j];
}
}
}
QueryPerformanceCounter(&nEndTime); //执行完数据
cost1_time=(double)(((nEndTime.QuadPart-nBeginTime.QuadPart) *1000.0) /nFreq.QuadPart); //相减得到数据除精度
QueryPerformanceCounter(&nBeginTime);
Make(n-1,tw);
QueryPerformanceCounter(&nEndTime);
cost2_time=(double)(((nEndTime.QuadPart-nBeginTime.QuadPart) *1000.0) /nFreq.QuadPart);
QueryPerformanceCounter(&nBeginTime);
for(j=0;j<=tw;j++)
if(j>=w[1])
g[1][j]=p[1];
else
g[1][j]=0;
for (i = 2; i <=n; i++)
for (j = 0; j <= tw; j++)
if(j>=w[i]&&g[i-1][j]<g[i-1][j-w[i]]+p[i])
g[i][j]=g[i-1][j-w[i]]+p[i];
else
g[i][j]=g[i-1][j];
cw=tw;
QueryPerformanceCounter(&nEndTime);
cost3_time=(double)(((nEndTime.QuadPart-nBeginTime.QuadPart) *1000.0) /nFreq.QuadPart);
printf("\t|%3d\t|%3d\t|%12g\t|%11g\t|%11g|\n",n,tw,cost1_time,cost2_time,cost3_time);
}
}
printf("|------------------------------------------------------------------|\n");
}
int main()
{
int a=4,b=5,d=1;
while(a!=3){
printf("\t\t\t1.算法检测\n");
printf("\t\t\t2.算法时间复杂度比较\n");
printf("\t\t\t3.退出\n");
printf("\t\t\t请选择:");
scanf("\t\t\t%d",&a);
printf("\n");
switch(a){
case 1:
while(b!=4){
printf("\t\t\t1.蛮力算法\n");
printf("\t\t\t2.递归算法\n");
printf("\t\t\t3.动态规划算法\n");
printf("\t\t\t4.退出\n");
printf("\t\t\t请选择:");
scanf("\t\t\t%d",&b);
printf("\n");
switch(b){
case 1:
d=1;
while(d!=2){
force();
printf("\t\t\t1.继续蛮力算法\n");
printf("\t\t\t2.退出\n");
printf("\t\t\t请选择:");
scanf("\t\t\t%d",&d);
printf("\n");
}
break;
case 2:
d=1;
while(d!=2){
recursive();
printf("\t\t\t1.继续递归算法\n");
printf("\t\t\t2.退出\n");
printf("\t\t\t请选择:");
scanf("\t\t\t%d",&d);
printf("\n");
}
break;
case 3:
d=1;
while(d!=2){
dynamic();
printf("\t\t\t1.继续动态规划算法\n");
printf("\t\t\t2.退出\n");
printf("\t\t\t请选择:");
scanf("\t\t\t%d",&d);
printf("\n");
}
break;
case 4:
break;
default:
printf("\t\t\t请重新选择:\n");
break;
}
}
break;
case 2:
d=1;
while(d!=2){
compareTime();
printf("\t\t\t1.继续时间复杂度比较\n");
printf("\t\t\t2.退出\n");
printf("\t\t\t请选择:");
scanf("\t\t\t%d",&d);
printf("\n");
}
break;
case 3:
break;
default:
printf("\t\t\t请重新选择:\n");
break;
}
}
}