装箱问题(Packing DP)

有一个箱子容量为V（正整数,0<=V<=20000）,同时有n个物品(0<n<=30),每个物品有一个体积(正整数)。

要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

<input>

第一行为一个正整数V表示箱子的容量，第二行一个正整数N表示物品个数，接下来N行列出这N个物品各自的体积。

单独一行，表示箱子最小的剩余空间。

 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 }

<问题分析>

经典的0/1背包问题，设置一个BOOL数组来存取状态，和一个INT数组进行倒序遍历。

状态转换方程:opt[j]=opt[j-w[i]]{opt[j]=true;j-w[i]>0}