题目：UVA - 10280Old Wine Into New Bottles(完全背包+剪枝）
题目大意：现在要将旧酒装入新瓶中，每种瓶子都有最小最大的容量要求，然后给你L升酒，在给你N个瓶子，每中瓶子的规格说明也给你，每个种类的瓶子的供应是无限的，问怎样子安排这些酒才能使得剩余的酒最少。
解题思路：这题是完全背包的题目，但是一开始就被这题的数据吓到，10^9ML，然后还有100个瓶子，瓶子的最大最小容量还相差4000左右，直接去完全背包肯定超时。之后看了大神的题接，有个规律：每个种类的瓶子的最大最小的容量是连续的，这样多次用这种瓶子，会使得最小和最大的容量值越来越靠近，最终达到了重叠的部分。所以（k + 1）* min > k * max, 这样从k * min开始后面的酒就一定可以装完。 这个是一个很大的剪枝，并且这题还要考虑容量重复的情况，用vis数组记录一下。
代码：
#include <cstdio>
#include <cstring>
const int maxn = 1e8 + 5;
const int N = 105;
const int M = 4505;
int dp[maxn];
int v[N][2];
int vis[M];
int l, n;
void init () {
memset (dp, 0, sizeof (dp));
memset (vis, 0, sizeof (vis));
for (int i = 0; i < n; i++)
for (int j = v[i][0]; j <= v[i][1] && j <= l; j++)
if (!vis[j])
vis[j] = 1;
dp[0] = 1;
}
int main () {
int t;
int maxc, minc;
scanf ("%d", &t);
while (t--) {
maxc = -1;
minc = M;
scanf ("%d%d", &l, &n);
l *= 1000;
int k = -1;
for (int i = 0; i < n; i++) {
scanf ("%d%d", &v[i][0], &v[i][1]);
if (k < v[i][0] * v[i][0] / (v[i][1] - v[i][0]))
k = v[i][0] * v[i][0] / (v[i][1] - v[i][0]);
if (maxc < v[i][1])
maxc = v[i][1];
if (minc > v[i][0])
minc = v[i][0];
}
if (l >= k) {
printf ("0\n");
} else {
init ();
if (l <= maxc && vis[l]) {
printf ("0\n");
} else {
for (int i = minc; i <= maxc; i++)
for (int j = i; j <= l; j++) {
if (vis[i] && dp[j - i])
dp[j] = 1;
}
int i;
for (i = l; i >= 0; i--)
if (dp[i])
break;
printf ("%d\n", l - i);
}
}
if (t)
printf ("\n");
}
return 0;
}