0-1背包

http://acm.hdu.edu.cn/showproblem.php?pid=2602

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #define maxn 1005
 5 using namespace std;
 6 int n,v;
 7 int f[maxn][maxn];
 8 int c[maxn],w[maxn];
 9 int main()
10 {
11     //freopen("in.txt","r",stdin);
12     int t;
13     scanf("%d",&t);
14     while(t--)
15     {
16         scanf("%d%d",&n,&v);
17         for(int i=1;i<=n;i++)
18             scanf("%d",&w[i]);
19         for(int i=1;i<=n;i++)
20             scanf("%d",&c[i]);
21         memset(f,0,sizeof(f));
22         for(int i=n;i>=1;i--)
23             for(int j=0;j<=v;j++)
24             {
25                 if(i==n)
26                     f[i][j]=0;
27                 else
28                     f[i][j]=f[i+1][j];
29                 if(j>=c[i])
30                 f[i][j]=max(f[i][j],f[i+1][j-c[i]]+w[i]);
31             }
32         int ans=0;
33         for(int i=1;i<=n;i++)
34             ans=max(ans,f[i][v]);
35         printf("%d
",ans);
36     }
37     return 0;
38 }

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #define maxn 10005
 5 using namespace std;
 6 int n,v;
 7 int f[maxn];
 8 int c[maxn],w[maxn];
 9 int main()
10 {
11     //freopen("in.txt","r",stdin);
12     int t;
13     scanf("%d",&t);
14     while(t--)
15     {
16         scanf("%d%d",&n,&v);
17         for(int i=1;i<=n;i++)
18             scanf("%d",&w[i]);
19         for(int i=1;i<=n;i++)
20             scanf("%d",&c[i]);
21         memset(f,0,sizeof(f));
22         for(int i=1;i<=n;i++)
23             for(int j=v;j>=c[i];j--)
24             f[j]=max(f[j],f[j-c[i]]+w[i]);
25         printf("%d
",f[v]);
26     }
27     return 0;
28 }

View Code