HDU 2602 Bone Collector(01背包)
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 ?
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.
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
这道题目是一道裸01背包的动态规划问题。
利用数组dp[i][j]记录从第i个物品开始挑选总重小于j时,总价值的最大值。于是得到递推式:
dp[n+1][j]=0
dp[i][j]=dp[i+1][j](j<Bone_volume[i])
dp[i][j]=max(dp[i+1][j],dp[i+1][j-Bone_volume[i]]+Bone_value[i])(其他)
当所剩背包容量不足以装下Bone_volume[i]时则跳过i(不装i),dp[i][j]=dp[i+1][j],否则在装i(dp[i][j]=dp[i+1][j])和不装i(dp[i][j]=dp[i+1][j-Bone_volume[i]]+Bone_value[i])中选择最大值。
AC代码:
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1010;
const double eps = 1e-5;
const double e = 2.718281828459;
ll Case_num, Bone_num, Bag_Volume;
ll Bone_value[maxn], Bone_volume[maxn];
ll dp[maxn][maxn];
void Dynamic_programming_from_back() {
for (int i = Bone_num; i >= 1; --i) {
for (int j = 0; j <= Bag_Volume; ++j) {
if (j < Bone_volume[i]) {
dp[i][j] = dp[i + 1][j];
}
else {
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - Bone_volume[i]] + Bone_value[i]);
}
}
}
}
void Get_information() {
cin >> Case_num;
while (Case_num--) {
mem(Bone_value, 0);
mem(Bone_volume, 0);
cin >> Bone_num >> Bag_Volume;
for (int i = 1; i <= Bone_num; ++i) {
cin >> Bone_value[i];
}
for (int i = 1; i <= Bone_num; ++i) {
cin >> Bone_volume[i];
}
mem(dp, 0);
Dynamic_programming_from_back();
cout << dp[1][Bag_Volume] << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
Get_information();
return 0;
}
这个代码动态规划中i循环是逆向的。
dp[i][j]:从0到i这i+1个物品中选出总重量不超过j的物品时总价值的最大值。
如此定义则关于i的循环就能正向进行。递推式:
dp[1][j]=0
dp[i+1][j]=dp[i][j](j<Bone_volume[i])
dp[i+1][j]=max(dp[i][j],dp[i][j-Bone_volume[i]]+Bone_value[i](其他)
AC代码:
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1010;
const double eps = 1e-5;
const double e = 2.718281828459;
ll Case_num, Bone_num, Bag_Volume;
ll Bone_value[maxn], Bone_volume[maxn];
ll dp[maxn][maxn];
void Dynamic_programming_from_front() {
for (ll i = 1; i <= Bone_num; ++i) {
for (ll j = 0; j <= Bag_Volume; ++j) {
if (j < Bone_volume[i]) {
dp[i + 1][j] = dp[i][j];
}
else {
dp[i + 1][j] = max(dp[i][j], dp[i][j - Bone_volume[i]] + Bone_value[i]);
}
}
}
}
void Get_information() {
cin >> Case_num;
while (Case_num--) {
mem(Bone_value, 0);
mem(Bone_volume, 0);
cin >> Bone_num >> Bag_Volume;
for (int i = 1; i <= Bone_num; ++i) {
cin >> Bone_value[i];
}
for (int i = 1; i <= Bone_num; ++i) {
cin >> Bone_volume[i];
}
mem(dp, 0);
Dynamic_programming_from_front();
cout << dp[Bone_num + 1][Bag_Volume] << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
Get_information();
return 0;
}