本文主要是介绍【HDU】2602 Bone Collector，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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 ?
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 2^31).
Sample Input
1 5 10 1 2 3 4 5 5 4 3 2 1
Sample Output
14
思路
这个是典型的01背包问题。
（1）状态方程为dp[j] = max(dp[j], dp[j-volume[i]] + value[i])。dp[j]为背包容量为j时最大总价值，volume[i]为遇到第i块骨头时骨头的大小，value[i]为此骨头的价值。
当放入骨头i时，有两种状态：（1）放入：即dp[j-volume[i]] + value[i]；（2）不放入：即dp[i]
（2）初始条件：dp = 0
（3）边界条件：无
（4）计算顺序：无要求。
代码
#include <iostream>
#include <algorithm>
using namespace std;int main() {std::ios::sync_with_stdio(false);int T, N, V;int value[1001], volume[1001], bag[1001];cin >> T;while (T--) {memset(bag, 0, sizeof(bag));cin >> N >> V;for (int i = 0; i < N; i++) cin >> value[i];for (int i = 0; i < N; i++) cin >> volume[i];for (int i = 0; i < N; i++)for (int j = V; j >= volume[i]; j--)bag[j] = max(bag[j], bag[j - volume[i]] + value[i]);cout << bag[V] << endl;}return 0;
}
这篇关于【HDU】2602 Bone Collector的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
