注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

HDU 2602 01背包  

2014-05-14 23:48:09|  分类: 背包 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

许多年前,在特迪的家乡有一个人叫“骨头”。不同的骨头,这人喜欢收集走进了坟墓

骨收藏家与体积V一大袋他的旅行收集很多骨很明显,不同骨具有不同的价值和不同体积现在由于各骨的价值随着他的旅行你能计算出收集器可以获得总价值最大

输入

第一行包含一个整数t,病例数

其次是T的案例,每个案例三行,第一行包含两个整数N,V,(n≤1000,V<=1000)为代表的骨头的数量和他的袋体积。第二行包含N个整数,代表各骨的价值。第三行包含N个整数,表示每个体积

输出

一个整数,每行代表最大总价值(这个数字将低于231

#include <iostream>
#include <cstring>
using namespace std;
int dp[1001], v[1000], p[1000];
inline int max(int a, int b) { return a>b?a:b; }
int main()
{ int c;
scanf("%d", &c);
while (c--) {
int n, V, i, j;
scanf("%d %d", &n, &V);
for (i=0; i<n; i++) scanf("%d", &p[i]);
for (i=0; i<n; i++) scanf("%d", &v[i]);
memset(dp, 0, sizeof(dp));
for (i=0; i<n; i++)
for (j=V; j>=v[i]; j--)
dp[j] = max(dp[j], dp[j-v[i]] + p[i]);
printf("%d\n", dp[V]);
}
}



  评论这张
 
阅读(1)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017