【01背包】HDU 2602 Bone Collector (模板题)
2024-10-03 10:44:18
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
HDU 1st “Vegetable-Birds Cup” Programming Open Contest
思路:01背包裸题。01背包:有限的背包容量取最大的价值,每样东西选择取或不取
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std; long long va[];
int vo[];
long long dp[]; int main()
{
int T,n,v,i,j;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&v);
for(i=;i<=n;i++)
scanf("%lld",&va[i]);
for(i=;i<=n;i++)
scanf("%d",&vo[i]);
memset(dp,,sizeof(dp));
for(i=;i<=n;i++)
{
for(j=v;j>=vo[i];j--)
{
dp[j]=max(dp[j],dp[j-vo[i]]+va[i]);
}
}
printf("%lld\n",dp[v]);
}
return ;
}
最新文章
- springmvc session和model解析
- mysql 主主互备
- SDRAM,DRAM,SRAM,DDR的概念
- JVM生产环境参数实例及分析
- 用Session实现验证码
- C# Thread多线程学习
- Erlang千万级用户游戏框架(Openpoker)源码文件分析清单
- R系列:分词、去停用词、画词云(词云形状可自定义)
- Java面试11|Maven与Git
- business expressions(二)
- TCP/IP的四元组、五元组、七元组
- centos6.5-VMware虚拟机-双网卡绑定
- c# 封装Dapper操作类
- python 全栈开发,Day76(Django组件-cookie,session)
- MVC无刷新上传图片并显示
- ASP.NET WebForm Form表单如何实现MVC那种“自动装配”效果呢?
- SVN:项目管理工具
- 不使用库函数sqrt实现求一个数的平方根
- C++11 中的 Defaulted 和 Deleted 函数
- Win32窗口创建过程