首页 > 代码库 > HDU Bone Collector 2620 01背包

HDU Bone Collector 2620 01背包

01背包模板式的题目,套模板或者直接敲就可以了。

Bone Collector


#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <limits.h>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;

const int MAX_N = 1001;

struct Bone
{
	int val, vol;
};
Bone bos[MAX_N];
long long dp[MAX_N];
int N, V;

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d %d", &N, &V);
		
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &bos[i].val);
		}
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &bos[i].vol);
		}
		fill(dp, dp+V+1, 0LL);
		for (int i = 0; i < N; i++)
		{
			for (int j = V; j >= bos[i].vol; j--)
			{
				if (dp[j] < dp[j-bos[i].vol] + (long long)bos[i].val)
					dp[j] = dp[j-bos[i].vol] + (long long)bos[i].val;
			}
		}
		printf("%I64d\n", dp[V]);
	}
	return 0;
}



HDU Bone Collector 2620 01背包