例题HDU-2602
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 231).
Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1
Sample Output
14
二维数组dp[][]
以下是代码
#include<vector>
#include<iostream>
using namespace std;
int maxBoneValue(int n,int V,vector<int>& value,vector<int>& volumes)
{
vector<vector<int>> dp(n+1,vector<int>(V+1,0));
//i表示前i个骨头
for(int i = 1;i<=n;i++)
{
//j代表当前背包的容量，当j=0时，意味着背包的容量为0
//dp[i][0]都是0,当我们数组初始化时，已经隐含了j=0的情况，所以从1开始
for(int j= 1;j<=V;j++)
{
//不选这个骨头，如果装不下
if(j<volumes[i-1])
{
//这个判断 j < volumes[i-1] 是为了检查当前的背包容量 j 是否足够来装下第 i 个骨头。
//volumes[i-1] 是第 i 个骨头的体积（因为数组是从0开始的，所以第 i 个骨头的体积在 volumes 数组中的索引是 i-1）
//j代表当前背包容量
dp[i][j] = dp[i-1][j];
}
else{
//考虑这个骨头情况
dp[i]