写了个思想：欢迎提供一下意见！

解题思想与上界证明：

题意是：有一些酒，和一些酒瓶，需要用酒瓶来装这些酒，但是装酒瓶时，每瓶不能太满也不能十分不满，满的话受热膨胀会挤出瓶塞，太少的话，空气就多，酒就会变质。现在希望把酒装进酒瓶后剩下的酒最少，求这个最少值！酒的量十分大：1000000000（10亿）
一道有一个剪枝的背包DP。

剪枝方法：

可以想象 ，给出酒的量太大了，即使是线性时间运行都会超时！
想象一下，它可能是量大到一定的时候是一定一点不剩的！那么什么是其最大值呢！
其实最大值为450000就足够了！ 证明如下

现假设有很多很多的酒，那么它肯定能装满很多瓶，可能有一瓶是剩余的！（概率十分大）假设剩余约为0%（其实是不能等于0%的，否则就是刚好装到一点不剩的状态，约为0%是最坏的情况），那么就可以从那些满的状态把酒给那个只有一点酒的瓶子中，最坏的情况是可以把1%酒给它，那么至少需要这样的满瓶是99瓶！所以，上界值就是  ：  99*Max(L)+1  （加1是因为那瓶酒剩1ml，这是最坏情况）。这里的最满是4500ml，那么代入公式：
99*4500+1=445501.上界为445501 。其实上界可以根据实际给出的数字求出来的，这样的剪枝就更好了！能更省时间！

然后就是DP了！
枚举最大和最小值背包DP，就行了！然后加一个
	int tap=0;
	for (i=0;i<n;i++)
	{
		for (j=minl[i];j<=maxl[i];j++)
		{
			if(dp[j])
			{
				tap=1;
				break;
			}
		}
		if(tap) break;
	}
就可以AC了！ 可以证明为什么只枚举最大和最小值。
可以想象两种情况：
1.一定有剩余的情况，那么有一个瓶是少于下界值的，其他的瓶都是最满的.
2.假设刚好装下。那么就可以把一些大于某些瓶上界的酒移到，快全满的酒瓶中，一直移，最终能达到，一些瓶是全满的，一些瓶是刚好满的，一个瓶介于最满与最不满之间。对于这个瓶，通过上面的两重循环就可以判断。其他最满和最不满枚举最大和最小值的背包DP就行了。

• 顶大牛！ (8) 1272407027 2009-10-06 10:09:53
• 此题好的做法是dijkstra (1034) angela_channg 2009-10-06 10:12:51
  • Re:此题好的做法是dijkstra (17) 1272406003 2009-10-06 10:29:39
• Re:剪枝的背包DP！ 上界可以证明 (30) majia__ 2010-08-21 11:03:00