初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。
有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别
这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，
这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设
为0。
为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合
法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好
装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果
背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，
所以初始时状态的值也就全部为0了。
第一种方法：转化为01背包问题求解既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背
包问题转化为01背包问题来解。最简单的想法是，考虑到第i种物品最多选V/c[i]件，于是可以把
第i种物品转化为V/c[i]件费用及价值均不变的物品，然后求解这个01背包问题。这样完全没有改
进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一
种物品拆成多件物品。
f[i][v] = max{ f[i - 1][v - k * c[i]] + k * w[i] } 0<= k <= v
在OJ上内存超出，但感觉应该是正确的，贴上代码：
1 #include <stdio.h> 2 #include<string.h> 3 const int INF=0x80000000; 4 int f[2005][50005]; 5 int c[2005],v[2005]; 6 int main() 7 { 8 int i,j,k,n,C,N,max; 9 scanf("%d",&N); 10 while(N--){ 11 scanf("%d%d",&n,&C); 12 for(i=0;i<=n;i++){ 13 for(j=0;j<=C;j++) 14 f[i][j]=INF; 15 f[i][0]=0; 16 } 17 for(i=1;i<=n;i++) 18 scanf("%d%d",&c[i],&v[i]); 19 for(i=1;i<=n;i++){ 20 for(j=0;j<=C;j++){ 21 int max=INF; 22 for(k=0;k<=j/c[i];k++){ 23 if(f[i-1][j-k*c[i]]+k*v[i]>max) 24 max=f[i-1][j-k*c[i]]+k*v[i]; 25 } 26 f[i][j]=max; 27 } 28 } 29 if(f[n][C]>0) printf("%d\n",f[n][C]); 30 else puts("NO"); 31 } 32 return 0; 33 }
第二种方法使用滚动数组,其代码和01背包类似，仅仅是把j的递推顺序改成从小到大递推了，之所以要这样我感觉是01背包一种物品不能被选用多次，为了简化空间去掉一维空间，就需要避免
后面的上一次的f[i][j]被这次重新覆盖而对下次循环产生不正确的结果，所以要从大往小推，即从后往前推,本次的f[i][j]恰是上次的f[i-1][j]推来的，而不是本次f[i][j]得来的，而对于完全背包
问题恰好是利用了这种规律，因为一件物品可以选取多次，在推倒f[i][j]时就需要包含前面f[i][j]以达到前面物品可以被使用多次的情况！贴上AC的代码：
1 #include <stdio.h> 2 const int INF=0x80000000; 3 int f[50005]; 4 int max(int a,int b){ 5 return a>b?a:b; 6 } 7 int main() 8 { 9 int i,j,n,c,v,C,N; 10 scanf("%d",&N); 11 while(N--){ 12 scanf("%d%d",&n,&C); 13 for(i=1;i<=C;i++) 14 f[i]=INF; 15 f[0]=0; 16 for(i=1;i<=n;i++){ 17 scanf("%d%d",&c,&v); 18 for(j=c;j<=C;j++) //从前往后递推，这样才能保证一种物品可以被使用多次 19 f[j]=max(f[j-c]+v,f[j]); 20 } 21 if(f[C]>0) printf("%d\n",f[C]); 22 else puts("NO"); 23 } 24 return 0; 25 }