<Description>
有一個箱子容量為V（正整數,0<=V<=20000）,同時有n個物品(0<n<=30),每個物品有一個體積(正整數)。
要求n個物品中，任取若幹個裝入箱内，使箱子的剩餘空間為最小。
<input>
第一行為一個正整數V表示箱子的容量，第二行一個正整數N表示物品個數，接下來N行列出這N個物品各自的體積。
<output>
單獨一行，表示箱子最小的剩餘空間。
<input example>
24
6
8
3
12
7
9
7
1 #include <stdio.h>
2 #include <string.h>
3
4 int main()
5 {
6 bool val[20001];
7 memset(val,0,sizeof(bool)*20001);
8 int i,j,V,n,w[31];
9 scanf("%d",&V);
10 scanf("%d",&n);
11 for(i=1;i<=n;i++)
12 scanf("%d",&w[i]);
13 val[V]=true;
14 for(i=n;i>0;i--)
15 {
16 for(j=V;j>=0;j--)
17 {
18 if(val[j]&&j-w[i]>=0)
19 {
20 val[j-w[i]]=true;
21 }
22 }
23 }
24 for(j=0;j<=V;j++)
25 {
26 if(val[j]) break;
27 }
28 printf("%d",j);
29 while(true);
30 return 0;
31 } <output example>
<問題分析>
經典的0/1背包問題，設定一個BOOL數組來存取狀态，和一個INT數組進行倒序周遊。
狀态轉換方程:opt[j]=opt[j-w[i]]{opt[j]=true;j-w[i]>0}
