hdu2602

maksyuki 发表于 oj 分类，标签: DP-背包

15 9月 2015

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³¹).

Sample Input

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

题目类型：01背包

算法分析： 直接使用就地滚动求解即可，注意这里的背包没限制一定要装满

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 50000 + 66;

int dp[maxn], c[maxn], w[maxn];

int main()
{
//    ifstream cin ("aaa.txt");

    int n, m ,t;
    cin>> t;

    while (t--)
    {
        cin >> n >> m;

        for (int i = 0;i < n; i++)
            cin >> w[i];

        for (int i = 0;i < n;i++)
            cin >> c[i];


        memset (dp, 0, sizeof (dp));
        for (int i = 0; i < n; i++)
        {
            for (int j = m; j >= c[i]; j--)
            {
                dp[j] = max (dp[j], dp[j-c[i]] + w[i]);
            }
        }

        int maxval = -INF;
        for (int i = 0; i <= m; i++)
            maxval = max (maxval, dp[i]);

        cout << maxval << endl;
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 50000 + 66;

int dp[maxn], c[maxn], w[maxn];

int main()

{

// ifstream cin ("aaa.txt");

int n, m ,t;

cin>> t;

while (t--)

{

cin >> n >> m;

for (int i = 0;i < n; i++)

cin >> w[i];

for (int i = 0;i < n;i++)

cin >> c[i];

memset (dp, 0, sizeof (dp));

for (int i = 0; i < n; i++)

{

for (int j = m; j >= c[i]; j--)

{

dp[j] = max (dp[j], dp[j-c[i]] + w[i]);

}

int maxval = -INF;

for (int i = 0; i <= m; i++)

maxval = max (maxval, dp[i]);

cout << maxval << endl;

}

return 0;

}

hdu2594

hdu2669

一	二	三	四	五	六	日
« 6月
						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	28	29
30	31

超客的水墨烟雨

hdu2602

Bone Collector

分类目录

标签云

书签

近期评论