【问题描述】
背包是个好东西，希望我也有。
给你一个二维的背包，它的体积是。现在你有一些大小为和的物品，每个物品有自己的价值。你希望往背包里面装一些物品，使得它们的价值和最大，问最大的价值和是多少。
【输入格式】
第一行一个整数代表该测试点的数据组数。
对于每组数据，第一行有四个整数，其中分别代表大小为和大小为的物品个数。
接下来一行有个数代表每个物品的价值。
接下来一行有个数代表每个物品的价值。
【输出格式】
对于每组询问，输出能够达到的价值最大值。
【样例输入】
1
2 3 2 2
1 2
1 2
【样例输出】
4
这题居然不是 DP ！！！
好吧, DP和贪心傻傻分不清, 不过更倾向于DP, 因为贪心是个很玄学的存在(关键是证明啊！！！).
说一下贪心策略 :
对于 n×m 的网格放 1×2 和 1×3 的方块, 我们枚举放多少 1×2 和多少 1×3 的方块, 比如放 x个1×2 和 y个1×3的方块, 判断是否能放下, 若能放下, 肯定是取方块中价值最大的(体积都一样, 干嘛不取价值大的)
有以下结论(求证明):
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAX = 20010;
LL T = 0, n = 0, m = 0, p = 0, q = 0, ans = 0, sum = 0, tot = 0;
LL a[MAX] = { 0 }, b[MAX] = { 0 };
LL s[MAX] = { 0 }, t[MAX] = { 0 };
bool cmp(LL x, LL y) {
return x > y;
}
/***************************
Description: 重载min(LL, LL)
***************************/
LL min(LL A, LL B) {
return A < B ? A : B;
}
int main() {
scanf("%d", &T);
while(T --) {
scanf("%d %d %d %d", &n, &m, &p, &q);
for(int i = 1; i <= p; i ++) scanf("%d", &a[i]);
for(int i = 1; i <= q; i ++) scanf("%d", &b[i]);
sort(a + 1, a + p + 1, cmp);
sort(b + 1, b + q + 1, cmp);
for(int i = 1; i <= p; i ++) s[i] = s[i - 1] + a[i];
for(int i = 1; i <= q; i ++) t[i] = t[i - 1] + b[i];
ans = 0;
if(n == 2 || m == 2) {
if(m == 2) swap(n, m);
int l = m - m % 3; l = l / 3 * 2;
for(int i = 0; i <= min(q, l); i ++) {
tot = n * m - i * 3;
ans = max(ans, t[i] + s[min(p, tot / 2)]);
}
cout << ans << endl;
continue;
}
for(int i = 0; i <= q; i ++) {
if(n * m >= i * 3) {
tot = n * m - i * 3;
ans = max(ans, t[i] + s[min(p, tot / 2)]);
}
else break;
}
cout << ans << endl;
}
return 0;
}