NYOJ289 苹果

原先用的滚动数组，现在用基本的动态规划，结果调试了很多次，发现了原因，贴上改正后的代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 int v[1005],c[1005];
 4 int f[1005][1005];
 5 int max(int a,int b){
 6     if(a>b) return a;
 7     return b;
 8 }
 9 int main()
10 {
11     int i,j,n,C;
12     while(scanf("%d%d",&n,&C),n||C){
13         memset(f,0,sizeof(f));
14         for(i=1;i<=n;i++)
15             scanf("%d%d",&c[i],&v[i]);
16         for(i=1;i<=n;i++)
17             for(j=0;j<=C;j++){   //也可以改为j从C到0
18                 f[i][j]=f[i-1][j];  //忘记了当 j<c[i]时，需
19                         //要把当前f[i-1][j]的值传递过去，WA了很多次 
20                 if(j>=c[i])
21                     f[i][j]=max(f[i-1][j-c[i]]+v[i],f[i-1][j]);
22             }
23         printf("%d\n",f[n][C]);
24     }
25     return 0;
26 }

滚动数组解法：

#include<stdio.h>
int main()
{
    int i,j,n,v,c,w;
    while(scanf("%d%d",&n,&v)&&n||v)
    {
        int price[1001]={};
        for(i=0;i<n;i++)
        {        
            scanf("%d%d",&c,&w);
            for(j=v;j>=c;j--)  //滚动数组j必须从大到小递推 ，
            //之所以这样是因为本次的 price[j] 需要从前一次的 price[j]得到 
                if(price[j]<price[j-c]+w)
                    price[j]=price[j-c]+w;
        }
        printf("%d\n",price[v]);
    }
    return 0;
}