欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Bone Collector 背包

程序员文章站 2022-07-16 12:11:40
...

Bone Collector
原题链接https://vjudge.net/contest/348156#problem/H
Bone Collector 背包
Bone Collector 背包
最基础的01背包求最大值
注意输入的骨头的价值和重量要一一对应

#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
long long v[10005];
long long w[10005];
long long dp[1000005];
int main()
{
	long long t;
	scanf("%lld",&t);
	while(t--)
	{
		memset(dp,0,sizeof(dp));
		memset(w,0,sizeof(w));
		memset(v,0,sizeof(v));
		long long n,v1,i,j;
		scanf("%lld %lld",&n,&v1);
		for(i=1; i<=n; i++)
		{
			scanf("%lld",&v[i]);
		}
		for(i=1; i<=n; i++)
		{
			scanf("%lld",&w[i]);
		}
		for(i=1; i<=n; i++)
		{
			for(j=v1; j>=w[i]; j--)
			{
				dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
			}
		}
		printf("%lld\n",dp[v1]);
	}
	return 0;
}
相关标签: 背包