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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二维数组dp[][]

以下是代码

#include
#include
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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27