请问这代码是 完全背包吗?
- C/C++ code
#include<stdio.h>#include<string.h>int c[20][1000];int knapsack(int m,int n){ int i,j,w[21],p[21]; //w重量 p价格 m容量 n个数 for(i=1;i<n+1;i++) scanf("%d%d",&w[i],&p[i]); memset(c,0,sizeof(c)); for(j=1; j<m+1; j++) c[1][j] = p[1]+(j-w[1])*p[1]; for(i=2;i<n+1;i++) { for(j=1;j<m+1;j++) { if(j%w[i] == 0) c[i][j] = c[i-1][j]>p[i]+(j-w[i])*p[i]?c[i-1][j]:(j-w[i])*p[i]; else c[i][j] = c[i-1][j]; } } return(c[n][m]); }int main(){ int m,n; while(scanf("%d%d",&m,&n)!=EOF) { printf("%d\n",knapsack(m,n)); } getchar(); getchar(); return 0;}
[解决办法]
看代码结构是完全背包
但好像有些错误,而且也没优化空间
其实下边伪代码就可以完成完全背包
for i=1..N //物品
for v=0..V //背包容量
f[v]=max{f[v],f[v-c[i]]+w[i]};