hdu2602 Bone Collector 01背包
2024-10-10 04:34:44
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 ?
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
题解:
在容量为m的背包中放入骨头,每个骨头有一定的体积和一定的价值,问如何装能使背包中背的骨头价值最大。典型的01背包问题,套用模板即可。
我写了两个,分别是一维数组和二维数组,一起发上来。
代码1:
#include <bits/stdc++.h> using namespace std;
int t,n,m,v[],w[],i,j,f[][];
int main()
{
cin>>t;
while(t--){
cin>>n>>m;
for(i=;i<=n;i++) cin>>v[i];
for(i=;i<=n;i++) cin>>w[i];
memset(f,,sizeof(f));
for(i=;i<=n;i++) //装入第i个骨头时,背包容量为j时的最大价值
for(j=;j<=m;j++){
if(j<w[i]){
f[i][j]=f[i-][j];
}
else{
f[i][j]=max(f[i-][j],f[i-][j-w[i]]+v[i]);
}
}
cout<<f[n][m]<<endl;
}
return ;
}
代码2:
#include <bits/stdc++.h> using namespace std;
int n,m,f[],v[],w[],i,j,t; int main()
{
cin>>t;
while(t--){
cin>>n>>m;
for(i=;i<=n;i++) cin>>v[i];
for(i=;i<=n;i++) cin>>w[i];
memset(f,,sizeof(f));
for(i=;i<=n;i++)
for(j=m;j>=w[i];j--){
if(f[j]<f[j-w[i]]+v[i])
f[j]=f[j-w[i]]+v[i];
}
cout<<f[m]<<endl;
}
return ;
}
最新文章
- 【原创】开源Math.NET基础数学类库使用(08)C#进行数值积分
- SQL注入攻击之关键字检测
- using System.Threading.Tasks;
- hadoop集群环境搭建之安装配置hadoop集群
- 不同css样式适应不同屏幕大小实现自适应宽度
- tensorflow import 没找到cudnn库问题解决
- 内层DIV超出后,出现滚动条问题
- SqlServer存储过程详解
- hive javaapi 002
- phpstorm使用zen coding 快速编辑补全html/css代码
- Java&#160;java&#160;jdk在Linux下安装与环境变量的配置
- C# Datatable排序(转)
- freemarker自己定义标签报错(二)
- leetcode237
- Redis学习十:Redis的复制(Master/Slave)【重要】
- 大数据竞赛平台——Kaggle 入门(转)
- Web开发:URL编码与解码(转)
- css动画 文字闪烁效果
- window.moveTo(),window.moveBy()不生效
- 操作 使用XML的方法