HDU--2602 Bone Collector(0-1背包)

题目:http://acm.hdu.edu.cn/showproblem.php?pid=2602 
分析:一个0-1背包问题。记得《背包九讲》的方法。

dp[j]=max{dp[j],dp[j-volume[i]]+value[i]}

#include<stdio.h>
#include<string.h>

int main()
{
  int num,c,n,value[1000],volume[1000],dp[1000];
  scanf("%d",&num);
  while (num--)
  {
    //数据输入
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)
      scanf("%d",&value[i]);
    for(int i=1;i<=n;i++)
      scanf("%d",&volume[i]);

    //初始化数据
    memset(dp,0,sizeof(dp));

    //利用方程递推
    for(int i=1;i<=n;i++)
      for(int j=c;j>=volume[i];j--)
        dp[j]=dp[j]>dp[j-volume[i]]+value[i]?dp[j]:dp[j-volume[i]]+value[i];

    printf("%d\n",dp[c]);
  }
  return 0;
}






HDU--2602 Bone Collector(0-1背包)

上一篇:Photoshop 漂亮的金色水晶字


下一篇:3dmax从建模到动画渲染讲解焦散动画