01背包:蒟蒻全WA求助!!
查看原帖
01背包:蒟蒻全WA求助!!
401723
言新楼主2021/1/22 14:21
#include<iostream>
using namespace std;
#include<algorithm>
#include<string.h>
int B[65][65];
int val[5][21];
int sum[5];
int  dp(int t ,int n)
{
	int nn;
	if (n == 1)
	{
		return sum[t];
	}
	memset(B, 0, sizeof(B));//清空背包
	int i, j;
	for(i =1;i<=n;i++)
		for (j = 1; j <= sum[t] / 2; j++)
		{
			if (val[t][i] > j)
				B[i][j] = B[i - 1][j];
			else
			{
			   B[i][j] = max(B[i - 1][j], B[i - 1][j - val[t][i]] + val[t][i]);
			}
		}
	return sum[t] - B[i-1][j-1];

}
int main()
{
	int s[5];
	cin >> s[1] >> s[2] >> s[3] >> s[4];
	for(register int j = 1;j<=4;j++)
	for (register int i = 1; i <=s[j] ; i++)
	{
		cin >> val[j][i];
		sum[j] += val[j][i];
	}
	cout << dp(1, s[1])+dp(2, s[2])+dp(3, s[3])+dp(4, s[4]);
	return 0;
}
2021/1/22 14:21
加载中...