初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。
有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。如果是第一种问法，要求恰好装满背包，那么在初始化时除了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 #include2 #include 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 #include2 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 }