今天做了一下背包专题，连接
http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=10736#overview密码是：sduacm 个人觉得这几题都很不错
额，第一题就不说了，普通的0－1背包
G题(HDU4091)是2011年上海区预赛第一题，据说AC这道题就可以拿铜牌了(囧) 题意是给俩个物品，每个物品有价值和体积，显然直接贪心不对，可以当作背包来解，但背包的容量很大，不能直接背包。这题的做法是：现求总容量对俩个物品的体积的LCM取余的余数，然后在余数中枚举，对其他的容量贪心，很容易证明这个思路的正确性。
HDU4091
//枚举即可破 因为只有俩种物品 找到俩种物品体积的lcm然后去余 对余数枚举
//然后对其他的贪心
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
LL gcd(LL a, LL b) {
return b ? gcd(b, a % b) : a;
}
int main() {
int t;
LL n, s1, v1, s2, v2;
while (scanf("%d", &t) != EOF) {
for (int cas = 1; cas <= t; cas++) {
scanf("%I64d%I64d%I64d%I64d%I64d", &n, &s1, &v1, &s2, &v2);
LL tmp = 2 * s1 * s2 / gcd(s1, s2);
LL tem = n / tmp;
n %= tmp;
if (tem) {
tem--; n += tmp;
}
LL res = max((tem)*(tmp/s1)*v1, (tem)*(tmp/s2)*v2);
LL temp = 0;
if (s2 > s1) {
swap(s1, s2);
swap(v1, v2);
}
for (int i = 0; i <= n / s1; i++)
if (temp < i*v1 + (n-i*s1)/s2*v2)
temp = i*v1 + (n-i*s1)/s2*v2;
res += temp;
printf("Case #%d: %I64d\n", cas, res);
}
}
return 0;
}
I题(SGU259)单机调度问题，题意是只有一个打印机，有许多传单需要打印和分发，打印的时间T[i]，分发的时间是L[i]，每个传单必须先打印后分发，假设有很多分发员，问将左右的传单打印并且分发完所用完的最短时间。这题直观有个感觉就是因为分发员有很多人，分发时间长的传单显然先打印比较好，并且很容易证明这个贪心思想的正确性。因此对L从大到小排序，然后再求的时间就是最短的时间。
SGU259
/*
* Author: whxnwjq
* Algorithm:
* File Name: I.cpp
*/
#include <map>
#include <queue>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <stack>
#include <set>
using namespace std;
#define PI acos(-1)
#define LL long long
const int inf = 0x7fffffff;
const double eps = 1e-6;
struct Node {
int t, l;
}a[222];
bool cmp(Node x, Node y) {
return x.l > y.l;
}
int main() {
int T, sum, tmp;
while (cin >> T) {
sum = 0, tmp = 0;
for (int i = 0; i < T; i++)
cin >> a[i].t;
for (int i = 0; i < T; i++)
cin >> a[i].l;
sort(a, a+T, cmp);
for (int i = 0; i < T; i++) {
sum += a[i].t; tmp -= a[i].t;
if (tmp < 0) tmp = 0;
tmp = max(a[i].l, tmp);
}
sum += tmp;
cout << sum << endl;
}
return 0;
}
SPOJ39_PIGBANK：这题是个经典的完全背包问题，题意是有个储蓄罐，知道了空的时候的质量和装满硬币的质量，给了一些硬币的质量和价值，求储蓄罐装满时硬币的最小价值。
经典题。
SPOJ39_PIGBANK
/*
* Author: phonism
* Algorithm: 完全背包经典题
* File Name: spoj39_PIGBANK.cpp
*/
#include <map>
#include <queue>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <stack>
#include <set>
using namespace std;
#define PI acos(-1)
#define LL long long
const int inf = 10101001;
const double eps = 1e-6;
int main() {
int t, n, m, a, u[1000], v[1000], dp[11000];
cin >> t;
while (t--) {
cin >> n >> m >> a;
for (int i = 1; i <= a; i++)
cin >> u[i] >> v[i];
for (int i = 0; i < 11000; i++)
dp[i] = inf;
dp[0] = 0;
for (int i = 1; i <= a; i++)
for (int j = v[i]; j <= m - n; j++)
dp[j] = min(dp[j], dp[j-v[i]] + u[i]);
if (dp[m-n] != inf) {
cout << "The minimum amount of money in the piggy-bank is ";
cout << dp[m-n] << "." << endl;
}
else puts("This is impossible.");
}
return 0;
}
HDU4091