hdoj - 2602 Bone Collector
2024-10-21 17:36:40
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
5 10
1 2 3 4 5
5 4 3 2 1
Sample Output
14
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
int a[],b[],dp[];
int main()
{
int t,n,v;
scanf("%d",&t);
for(int k=;k<t;k++)
{
memset(dp,,sizeof(dp));
scanf("%d %d",&n,&v);
for(int i = ;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int i = ;i<n;i++)
{
scanf("%d",&b[i]);
} for(int i = ;i<n;i++)
{
for(int j = v;j>=b[i];j--)
{
dp[j] = max(dp[j],dp[j-b[i]]+a[i]); //关键代码 }
}
printf("%d\n",dp[v]);
}
return ;
}
最新文章
- SDK接入(2)之Android Google Play内支付(in-app Billing)接入
- Excel大批量导入数据到SQLServer数据库-万条只用1秒
- 高性能JavaScript 重排与重绘
- User Settings in WPF
- 算法实践——Twitter算法面试题(积水问题)的线性时间解法
- Java 存储过程调用
- a trick in reading and storing file in the exact way!
- mysql忘记密码的处理方式(整理非原创)
- C++中数字与字符串之间的转换(使用CString.Format或者sprintf)
- 采购订单me22n 或者me21n增强 (点击保存和回车)
- 杭电ACM2020--绝对值排序
- axios的秘密
- angular,vue,react的基本语法—动态属性、事件绑定、ref,angular组件创建方式
- node里面的buffer理解
- 第二周javaweb学习进度表
- asp.net 动态更改 Request.Header
- Spring XML配置里的Bean自动装配
- Fiddler抓包分析
- JAVA EXAM2 复习提纲
- 使用GitHub Pages + Jekyll 建立博客