读书人

请教这代码是 完全背包吗

发布时间: 2012-03-03 15:33:03 作者: rapoo

请问这代码是 完全背包吗?

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]};

读书人网 >软件架构设计

热点推荐