hduoj 2602Bone Collector
2024-08-23 22:10:41
Bone Collector
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 40598 Accepted Submission(s):
16872
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 ?
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 ?
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.
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.
Output
One integer per line representing the maximum of the
total value (this number will be less than 231).
total value (this number will be less than 231).
Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1
5 10
1 2 3 4 5
5 4 3 2 1
Sample Output
14
Author
Teddy
Source
Recommend
#include<cstdio>
#include<cstring>
#include<iostream>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
#define max(a,b) (a>b?a:b)
int va[],vo[],dp[][];
int main()
{
//freopen("D:\\INPUT.txt","r",stdin);
int t,i,j;
int n,v;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&v);
for(i=; i<=n; i++)
{
scanf("%d",&va[i]);
}
for(i=; i<=n; i++)
{
scanf("%d",&vo[i]);
}
//dp[i][j] 前i件物品放入j体积的价值的最大值
//dp[i][j]=max(dp[i-1][j],dp[i-1][j-vo[i]]+va[i])
for(i=; i<=n; i++) //i体积
{
for(j=; j<=v; j++)
{
if(j>=vo[i]){
dp[i][j]=max(dp[i-][j],dp[i-][j-vo[i]]+va[i]);
}
else{
dp[i][j]=dp[i-][j];
} //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
}
}
printf("%d\n",dp[n][v]);
}
return ;
}
最新文章
- HTTP事务
- PHP命令行脚本接收传入参数的三种方式
- WPF系列:无边框窗口
- nginx学习
- BZOJ3993 [SDOI2015]星际战争
- CGI实现页面的动态生成
- git ssh key for github
- IOS设置button 图片 文字 上下、左右
- 多平台响应键盘事件!(适用于Cocos2dx 3.0 alpha以上版本号)
- 超级强大的SVG SMIL animation动画详解
- C语言语法笔记 – 高级用法 指针数组 指针的指针 二维数组指针 结构体指针 链表 | IT宅.com
- Spring Boot 系列教程14-动态修改定时任务cron参数
- Quartus14.1中Qsys创建custom component时编译出错原因
- R语言-探索两个变量
- PHP读取大文本文件并处理数据的思路
- Oracle 10g 应用补丁PSU 10.2.0.5.180717
- Resin安装配置
- 基于 OpenSSL 的 CA 建立及证书签发
- css学习_写法规范、选择器
- web环境中微信JS-SDK配置
热门文章
- nginx: [emerg] the ";ssl"; parameter requires ngx_http_ssl_module in /usr/local/nginx//conf/nginx.conf:117
- delay JS延迟执行
- web安全问题-csrf
- CF796D Police Stations 思维
- linux 环境下tomcat中部署jfinal项目
- [Leetcode]013. Roman to Integer
- 设置IIS,使客户端访问服务器上的文件
- Codeforces Round #532 (Div. 2)- B(思维)
- mysql 存储引擎介绍
- C#中Internal关键字的总结