01背包問題，01背包
1 //01背包問題
2 #include <stdio.h>
3 int w[20]; //重量
4 int p[20]; //價值
5 int c[20]; //選擇
6 int bag; //背包承重
7
8 int select(int m,int b)
9 {
10 //有m個物品，背包還能承重b，第m個物品拿還是不拿？
11 //如果拿，則總價值為v1=select(m-1,b-w[m])+p[m]
12 //如果不拿，則總價值為v0=select(m-1,b)
13 int v1,v0;
14
15 /* 邊界：
16 1. m=0,到了第一個物品，則只需要考慮還能不能拿得下
17 2. 背包的剩余承重b 小於 第m個物品的重量w[m]，第m個物品肯定不拿
18 */
19 if(m==0)
20 {
21 if(b>=w[m])
22 {
23 c[m]=1;
24 return p[m];
25 }
26 else
27 {
28 c[m]=0;
29 return 0;
30 }
31 }
32
33 if(b<w[m])
34 {
35 c[m]=0;
36 return select(m-1,b);
37 }
38
39 v1=select(m-1,b-w[m])+p[m];
40 v0=select(m-1,b);
41 //比較拿與不拿後的總價值，再做出決定
42 if(v0>v1)
43 {
44 c[m]=0;
45 return v0=select(m-1,b);
46 }
47 else
48 {
49 c[m]=1;
50 return v1=select(m-1,b-w[m])+p[m];
51 }
52 }
53
54 int main()
55 {
56 int i,n;
57 printf("請輸入物品數量:");
58 scanf("%d",&n);
59 printf("請輸入背包最大承重:");
60 scanf("%d",&bag);
61 printf("請輸入每件物品的重量:\n");
62 for(i=0;i<n;i++)scanf("%d",&w[i]);
63 printf("請輸入每件物品的價值:\n");
64 for(i=0;i<n;i++)scanf("%d",&p[i]);
65
66 printf("能獲得的最大價值為：%d\n方案為：\n",select(n-1,bag));
67 for(i=0;i<n;i++)
68 printf("%d ",c[i]);
69 printf("\n");
70 return 0;
71 }
72
