【问题描述】

背包是个好东西，希望我也有。
给你一个二维的背包，它的体积是???? × ????。现在你有一些大小为1 × 2和1 ×
3的物品，每个物品有自己的价值。你希望往背包里面装一些物品，使得它们的
价值和最大，问最大的价值和是多少。

【输入格式】

第一行一个整数????代表该测试点的数据组数。
对于每组数据，第一行有四个整数????, ????, ????
1
, ????
2，其中????
1
, ????
2分别代表大小为
1 × 2和大小为1 × 3的物品个数。
接下来一行有????
1
个数代表每个1 × 2物品的价值。
接下来一行有????
2
个数代表每个1 × 3物品的价值。

【输出格式】

对于每组询问，输出能够达到的价值最大值。

【样例输入】

1
2 3 2 2
1 2
1 2

【样例输出】

4

【样例解释】

庙里有座山。

【数据规模与约定】

对于20%的数据，????, ???? ≤ 10, ????1, ????2≤ 100。
对于70%的数据，????, ???? ≤ 100, ????1, ????2≤ 2000。
对于100%的数据，1 ≤ ???? ≤ 10,1 ≤ ????, ???? ≤ 500,0 ≤ ????1, ????2≤ 10000。

题解：

这道题看似背包型DP，其实不是，因为数据范围不允许，所以我们用贪心的思想来做（人生第一次用DP来骗贪心的分）
我们枚举放k个2个的块和n1+n2-k个3个的块，然后取最大值
就得到了答案

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int II[233333], III[233333];
bool cmp(int a, int b)
{
	return a > b;
}
int main()
{
	freopen("eyesight.in","r",stdin);
	freopen("eyesight.out","w",stdout);
	int t;
	cin >> t;
	while (t--)
	{
		int n, m, n1, n2;
		cin >> n >> m >> n1 >> n2;
		int s = n*m;
		for (int i = 1; i <= n1; i++)
			scanf("%d", &II[i]);
		for (int i = 1; i <= n2; i++)
			scanf("%d", &III[i]);
		if (n <= 1 && m <= 1)
			memset(II, 0, sizeof(II));
		if (n <= 2 && m <= 2)
			memset(III, 0, sizeof(III));
		sort(II + 1, II + n1 + 1, cmp);
		sort(III + 1, III + n2 + 1, cmp);
		for (int i = 1; i <= n1; i++)
			II[i] += II[i-1];
		for (int i = 1; i <= n2; i++)
			III[i] += III[i-1];
		int ans = 0;
		for (int i = 1; i <= n1 && (i << 1) <= s; i++)
			ans = max(ans, II[i] + III[min((s - i * 2) / 3, n2)]);
		printf("%d\n", ans);
	}
	return 0;
}