nyoj 289 苹果动态规划（java）

分析：0-1背包问题

第一次写了一大串，

时间：576 内存：4152

看了牛的代码后，恍然大悟；看来我现在还正处于鸟的阶段！

第一次代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef struct
 6 {
 7     int x;
 8     int y;
 9 }p;
10 p a[1001];
11 int b[1001][1001];
12 int cmp(p a,p b)
13 {
14     if(a.x==b.x)
15         return a.y<b.y;
16     else 
17         return a.x<b.x;
18 }
19 int max(int a,int b)
20 {
21     if(a>b)
22         return a;
23     return b;
24 }
25 int main()
26 {
27     int n,v,i,j;
28     while(scanf("%d%d",&n,&v)==2)
29     {
30         if(n==0&&v==0)
31             break;
32         memset(b,0,sizeof(b));
33         for(i=0;i<n;i++)
34             scanf("%d%d",&a[i].x,&a[i].y);
35         sort(a,a+n,cmp);
36         for(i=a[0].x;i<=v;i++)
37             b[0][i]=a[0].y;
38         for(i=1;i<n;i++)
39         {
40             for(j=a[0].x;j<=v;j++)
41                 if(j>=a[i].x)
42                 b[i][j]=max(b[i-1][j],b[i-1][j-a[i].x]+a[i].y);
43                 else b[i][j]=b[i-1][j];
44             //for(j=0;j<=v;j++)
45             //    printf("%d ",b[i][j]);
46         //    printf("
");
47         }
48         printf("%d
",b[i-1][v]);
49     }
50     return 0;
51 }

View Code

精简后的代码：

时间：160 内存：232

 1 #include<stdio.h>
 2 int main()
 3 {
 4     int i,j,n,v,c,w;
 5     while(scanf("%d%d",&n,&v)&&n||v)
 6     {
 7         int price[1001]={0};
 8         for(i=0;i<n;i++)
 9         { 
10             scanf("%d%d",&c,&w);
11             for(j=v;j>=c;j--) 
12                 if(price[j]<price[j-c]+w)
13                     price[j]=price[j-c]+w;
14         }
15         printf("%d
",price[v]);
16     }
17     return 0;
18 }

View Code

java：

nyoj 289 苹果 动态规划 （java）

nyoj 289 苹果动态规划（java）