HDU 2602 Bone Collectors(背包问题,模版)
2024-09-30 13:22:39
Bone Collector
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14336 Accepted Submission(s): 5688
Problem Description
Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
Input
The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
Output
One integer per line representing the maximum of the total value (this number will be less than 231).
Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1
Sample Output
14
Author
Teddy
Source
Recommend
lcy
这道题,我学会了,dp数组一定要放在主函数的外面,不然编译器就会崩!!!
这里的j起始要从0开始,这是十分恶心的地方,肯能就是volume=0也会有value!!!这个是个巨型的坑!!!!!
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[][];
int main()
{
int t;
cin>>t;
int n,m;
int w[],v[];
int f1,f2;
while(t--)
{
cin>>n>>m;
memset(w,,sizeof(w));
memset(v,,sizeof(v));
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)
{
cin>>v[i];
}
for(int i=;i<=n;i++)
{
cin>>w[i];
}
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(j<w[i]) dp[i][j]=dp[i-][j];
else
{
f1=i;
f2=j;
dp[i][j]=max(dp[i-][j],dp[i-][j-w[i]]+v[i]);
}
}
}
cout<<dp[f1][f2]<<endl;
}
return ;
}
最新文章
- jvm系列(六):jvm调优-从eclipse开始
- MVC中Control和View之间数据传递的方式
- SQL SERVER2012中使用游标来备份数据库
- maven相关概念
- Android中Listview实现分页加载效果OnScrollListener
- 使用solrj进行DIH操作
- Check the quota usage
- PhotoShop-CS4使用-----如何对psd进行简单切图
- [置顶] 【cocos2d-x入门实战】微信飞机大战之四:飞机登场咯
- sql server 行转列 Pivot UnPivot
- 设置webstorm缩写代码
- 一个非常好用的框架-AngularJS(一)
- 用于ViEmu的重置为试用状态的Python脚本
- mysql性能分析工具
- JavaScript自定义求和函数
- linux C++ 获取服务器外网IP地址(使用系统调用system)
- cocos子节点转父节点坐标 原理浅析(局部坐标转世界坐标同理)
- 数据适配:DataAdapter对象概述
- document.documentElement.scrollTop
- PHP二维数组按某个键值排序
热门文章
- 使用getCurrentPosition方法实时获取当前Geolocation信息(附源码文件)--html5、JavaScript
- Pytorch半精度浮点型网络训练问题
- linux常用网络命令ping和arping
- bat语法需要注意的地方
- js定义类
- leetcode-algorithms-23 Merge k Sorted Lists
- 22. Generate Parentheses C++回溯法
- python之命令行参数解析模块argparse
- virtualenv 运行python 解决依赖冲突问题 尤其是django那种蛋疼的版本问题
- 实验:输入一篇英文新闻,以“#”结束,统计其中a-z这26个字母各出现的次数和总字符个数。(不区分大小写)