0/1背包问题

例题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]