Hdu 2602 - Bone Collector
859 ワード
簡単な0-1リュックの問題
ゲージ方程式は、f[j]=max(f[j],f[j-v[i]+w[i])である.
MACコードは以下の通りである.
ゲージ方程式は、f[j]=max(f[j],f[j-v[i]+w[i])である.
MACコードは以下の通りである.
#include <stdio.h>
#include <string.h>
int n,v,w[1050],c[1050];
int dp[10000];
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
void pack(int cost,int weight)
{
int j;
for(j=v;j>=cost;j--)
dp[j]=max(dp[j],dp[j-cost]+weight);
}
int main()
{
int t,i;
scanf("%d",&t);
while(t--)
{
memset(dp,0,sizeof(dp));
scanf("%d %d",&n,&v);
for(i=0;i<n;i++)
scanf("%d ",&w[i]);
for(i=0;i<n;i++)
scanf("%d ",&c[i]);
for(i=0;i<n;i++)
pack(c[i],w[i]);
printf("%d
",dp[v]);
}
return 0;
}