HDU 2602-Bone Collector(01背包-一/二维)

谁践踏了优雅 2022-07-24 05:12 108阅读 0赞

# Bone Collector #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 47666 Accepted Submission(s): 19880**

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 ?  
![C154-1003-1.jpg][]

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

Author

Teddy

Source

[HDU 1st “Vegetable-Birds Cup” Programming Open Contest ][HDU 1st _Vegetable-Birds Cup_ Programming Open Contest]

Recommend

lcy | We have carefully selected several similar problems for you: [1203][] [2159][] [2955][] [1171][] [2191][]  
  
一维：

#include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int n[1001],v[1001];
    int dp[1001];
    int main()
    {
        int t;
        cin>>t;
        while(t--)
        {
            memset(dp,0,sizeof(dp));
            int num,vol,i,j;
            cin>>num>>vol;
            for(i=0; i<num; ++i)
                cin>>v[i];
            for(i=0; i<num; ++i)
                cin>>n[i];
            for(i=0; i<num; ++i)
                for(j=vol; j>=n[i]; --j)
                    dp[j]=max(dp[j],dp[j-n[i]]+v[i]);
            cout<<dp[vol]<<endl;
        }
        return 0;
    }

二维：

#include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int n[1001],v[1001];
    int dp[1001][1001];
    int main()
    {
        int t;
        cin>>t;
        while(t--)
        {
            int num,vol,i,j;
            cin>>num>>vol;
            for(i=0; i<num; ++i)
                cin>>v[i];
            for(i=0; i<num; ++i)
                cin>>n[i];
            for(i=0; i<num; ++i)
                for(j=0; j<=vol; ++j)
                    if(j<n[i]) dp[i+1][j]=dp[i][j];
                    else dp[i+1][j]=max(dp[i][j],dp[i][j-n[i]]+v[i]);
            cout<<dp[num][vol]<<endl;
        }
        return 0;
    }

[C154-1003-1.jpg]: /images/20220722/8044d239d67b4e01bcf86a427ec022b6.png
[HDU 1st _Vegetable-Birds Cup_ Programming Open Contest]: http://acm.hdu.edu.cn/search.php?field=problem&key=HDU+1st+%A1%B0Vegetable-Birds+Cup%A1%B1+Programming+Open+Contest&source=1&searchmode=source
[1203]: http://acm.hdu.edu.cn/showproblem.php?pid=1203
[2159]: http://acm.hdu.edu.cn/showproblem.php?pid=2159
[2955]: http://acm.hdu.edu.cn/showproblem.php?pid=2955
[1171]: http://acm.hdu.edu.cn/showproblem.php?pid=1171
[2191]: http://acm.hdu.edu.cn/showproblem.php?pid=2191