uva 10280(完全背包)

題意：有wine L的酒要放到n個瓶子裡，每個瓶子最少和最多放多少毫升酒給出，如果瓶子是無限多的，問酒最後最少剩餘多少毫升。

題解：相當于完全背包問題，f[i]表示imL的酒最少剩餘多少，因為瓶子的容量是個區間，是以直接把區間變成點，相當于a ～ b毫升的瓶子其實是有b - a個瓶子，容量分别是從a到b，如果隻是這樣做會逾時，因為酒最多會有1000000000ml，可以想一下，給了一個容量是725～750的瓶子，兩個這樣的瓶子容量會是1450 ~ 1500 ，三個這樣的瓶子容量是2175 ~ 2250，随着瓶子數量的增多，會出現區間重疊，這樣的話如果酒的量大于這個重疊區間的左值就一定可以全部裝進去。那麼剩餘量就是0，減少計算。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 105;
const int M = 21000000;
int wine, n, bot[N][2], num;
int f[M], vis[4510], cap[4510];

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &wine, &n);
		wine *= 1000;
		int lim = M;
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", &bot[i][0], &bot[i][1]);
			lim = min(lim, bot[i][0] * bot[i][1] / (bot[i][1] - bot[i][0]));
		}
		if (lim <= wine) {
			printf("0\n");
			if (t)
				printf("\n");
			continue;
		}
		memset(vis, 0, sizeof(vis));
		memset(f, 0, sizeof(f));
		num = 0;
		for (int i = 1; i <= n; i++)
			for (int j = bot[i][0]; j <= bot[i][1]; j++) {
				if (!vis[j]) {
					vis[j] = 1;
					cap[num++] = j;
				}
			}
		for (int i = 0; i < num; i++)
			for (int j = cap[i]; j <= wine; j++)
				f[j] = max(f[j], f[j - cap[i]] + cap[i]);
		printf("%d\n", wine - f[wine]);
		if (t)
			printf("\n");
	}
	return 0;
}