uva 10280 - Old Wine Into New Bottles(完全背包）
题目链接：10280 - Old Wine Into New Bottles
题目大意：现在有L升酒，以及n种酒瓶，现在给出每种酒瓶的最小容量和最大容量，每种酒瓶可以使用无限多次，问，怎样装酒，可以使得剩下的酒（即未能装进酒瓶中的酒）最少，输出最小值。
解题思路：刚开始直接背包，结果超时了，看了别人题解才知道要剪很大的枝，这里推荐一篇题解写的很仔细。
http://blog.csdn.net/yan_____/article/details/8671147
#include <stdio.h>#include <string.h>const int N = 105;const int M = 4505;const int MAX = 10000005;int n, v, dp[MAX], vis[M], top, sum;int l[N], r[N];void read() {top = 1 << 30;scanf("%d%d", &v, &n);v *= 1000;for (int i = 0; i < n; i++) {scanf("%d%d", &l[i], &r[i]);if (l[i] * r[i] / (r[i] - l[i]) < top)top = l[i] * r[i] / (r[i] - l[i]);}}void handle() {memset(vis, 0, sizeof(vis));for (int i = 0; i < n; i++) {for (int j = l[i]; j <= r[i] && j <= v; j++)vis[j] = 1;}}int solve() {memset(dp, 0, sizeof(dp));dp[0] = 1;for (int i = 0; i <= 4500; i++) {if (vis[i]) {for (int j = i; j <= v; j++) {if (dp[j - i])dp[j] = 1;}}}for (int i = v; i >= 0; i--)if (dp[i]) return i;}int main () {int cas;scanf("%d", &cas);while (cas--) {read();if (v >= top) printf("0\n");else {handle();if (v < M && vis[v]) printf("0\n");else printf("%d\n", v - solve());}if (cas) printf("\n");}return 0;}