为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/milk4
这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。
- 这是USACO Chapter 5 .3中的OI题目Milk Measuring的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。
[编辑] 问题分析
要用到迭代加深搜索(DFSID)。由于要求输出的是使用最少的牛奶桶，所以要先找牛奶桶数量为1的时候所有的组合，如果没有解再找牛奶桶数量为2...直到牛奶桶数量为P。
当搜索到一个组合，判断用这些牛奶桶是否能组成目标解的时候，可以用动态规划的方法来做。设f[i]是当需求的牛奶为i时，能否形成这个组合，是一个布尔型数组。
- 初始条件 f[0]=true
- 状态转移方程 f[i]=f[i] or f[ i-v[j] ] (j为使用的所有牛奶桶)
- 目标状态 f[Q]
- 如果f[Q]为true，则当前解合法，直接输出即可。
{但是如果仅仅这样写还是有一组数据过不去，需要进行一些优化。要优化动态规划的过程。
注意一个重要的信息，找到的组合中，每个牛奶桶至少用了一次。上面的状态转移方程中有许多某个牛奶桶使用0次的冗余状态。可以在初始的时候对(i=1..Q/v[第一个桶]) f[ i*v[第一个桶] ]赋值为true。对每个其他的桶的状态可以直接由前面的状态得出。
经过这个优化，数据就可以全过了。} {PS:如果在IDDFS的时候，每次到达叶节点才进行一次DP的话，TLE是必然的，但观察可知，每一层的DP状态均有父亲得来，因此可备份父亲状态的Boolean数组，每次递归完成后还原即可。速度不是很快，但是方便好写，也过了 Test 10: TEST OK [0.475 secs, 228 KB] 卡常数....
——Pollow
这里还有一个这样的优化，添加每一个点的时候，看看这个点是不是已有的桶的整数倍，如果是的话，这个点是完全没有必要添加的。最大一个点0.3S。
——songS
}
谁说裸DFSID+DP过不了。。。。。。。。
你把DP写成记忆化搜索不就行了。。。。。。
Test 1: TEST OK [0.000 secs, 2844 KB] Test 2: TEST OK [0.011 secs, 2844 KB] Test 3: TEST OK [0.000 secs, 2844 KB] Test 4: TEST OK [0.011 secs, 2844 KB] Test 5: TEST OK [0.000 secs, 2844 KB] Test 6: TEST OK [0.000 secs, 2844 KB] Test 7: TEST OK [0.022 secs, 2844 KB] Test 8: TEST OK [0.000 secs, 2844 KB] Test 9: TEST OK [0.022 secs, 2844 KB] Test 10: TEST OK [0.022 secs, 2844 KB]
快如闪电列。。。。。。。
详见C++源代码
致楼上诸位，DFSID+最优性剪枝可以秒杀。在递归判解之后、继续迭代之前判断当前桶子体积是否大于当前深度下的最优解，如果大于则剪枝。详见C++代码。
______________________________________________________________________________________________
[另一oier hydralisk 补充:这个优化可以过,但是不强,有的0.9*s才过. 还有个比较有效的优化,仅一组数据0.086s其他都0.000s.就是注意到大部分时间都是在2上消耗掉的,于是灵机一动,发现2的情况就是 ax+by=c 是否有>=1 的整数解! 剩下的就是简单的数学变形了: 首先 如果(a,b)|c 才有整数解,然后
a:=a div gcd(a,b)
b:=b div gcd(a,b)
c:=c div gcd(a,b) // 就是化简了 ax+by=c 使 (a,b)=1;
然后 x:=a mod b,y:=c mod b // 就是 x0*x≡y (mod b)
再求出一组特解 x0,带入 y0:=(c-a*x0)div b;
有 x=x0+b*t
y:=y0+a*t (t是整数)
再令x>0 ,y>0 解出t的范围,带回去,看有没有>=1 的解,有就直接输出.
此法+dfsid 相当快,思路清楚,程序很好写.] 程序可以见 http://freepascal.spaces.live.com/blog/cns!34840F274352AFEC!145.entry [-_-|| 个人blog]
貌似如果数据强的话，DFSID是过不了的。（个人见解）
可以用DP解决，DP方法如下所述。
维护字典序：
将桶体积降序排列；
对于每一层，维护一个rank数组，记录每个体积值的最优解字典序大小；
转移时，取many最小，且rank最小的转移，参见C++代码（ID:wwqqss21）；
（表述貌似不是很好，请后来的人协助修改）
SRC小菜的另一种思路：背包解法
可以用背包问题的思想来解答这道题。
用v[i]记录i号桶的体积，sel[i]记录i这个体积是否可以达到，many[i]记录i这个体积至少需要多少种不同体积的桶来得到，tj[i]记录i这个体积所需桶集中最大的那个桶的编号，pre[i]记录i这个体积是通过哪个体积拓展到的，可见（i-pre[i]) div v[tj[i]］为i这个体积所需桶集中最大的那个桶的数量。
初始化：sel[0]:=true;tj[0]:=-1;many[1..p]:=maxlongint;
主程序：外循环i枚举桶的编号，内循环j枚举体积，当体积已达到过时，对其向后连续拓展(k:=j+v[i],j+2*v[i]..直至超出p停止)，如果many[j]+1<many[k]那么更新。重要的:当many[j]+1=many[k]并且tj[j]<tj[pre[k]]时也要更新，这是为了保证集合的最优化。（大家可以好好想想这是为什么）
另外，细节决定成败。我因为对细节的优化使得程序由第七个点超时质变为AC，最慢的点0.097s!
请参看我的pascal程序。
上面的解法貌似是错的，错在“ 当many[j]+1=many[k]并且tj[j]<tj[pre[k]]时也要更新 ”，如果many[j]+1=many[k],还要暴力向前扫描两者方案来比较
试试这个数据： 155 6 20 61 74 30 43 82 答案是 3 20 61 74 而不是 3 30 43 82
解析三：
这道题可以用背包来解，方程也很简单，即 用f[i,j]表示前i个桶，构成容量j所需的最少桶的数量。 f[i,j] :=min(f[i-1,j],f[i-1,j-A[i]*k]+1); 其中A数组为每个桶的容量，k(1=<k<=j div A[i])第i个桶用的次数. 这样，关键在于最小字典序。 我没有太好的方法(O(1)),于是， 在更新是，我们可以对于达到f[j]的的相同桶数状态进行追溯，比较，取字典序较小的一个。 也可以用若干个数组记录此状态的第一最小关键字，第二最小关键字... 这样，比较是较容易，但更新时需要同时更新。 事实上，尽管这样复杂度看似很高,外循环i，内嵌j,k,还有更新的复杂度，但对付此题数据，完全没有问题。 (不超过0.2s).
当然，这样的复杂度是很大的，无论是时间，还是空间。 空间较好解决，把f[i,j]用f[j]替代，滚动数组。 而时间上，说一下不成熟的思路，（没试过），希望与大家共同进步。 注意到，所有更新f[i,j]的状态f[i-1,j-A[i]*k]+1，其中 j-A[i]*k不论k取何值，都对于模A[i]同余，因此可以归为一个等价类， 在维护时，可以用A[i]个队列(0..A[i]-1),保存余数为i的状态的值，因而 状态转移中的f[i-1,j-A[i]*k]+1一项变为在该队列1..j div A[i]中找 最小值，而j div A[i]会随j增加而增加，下界(也就是1)不降，于是，想到 用单调队列来维护，转移时间为O(1),省去了k的循环。
如果哪位神牛有解决字典序的方法，望与大家交流。
综合一下上述方法：
用v[i]记录i号桶的体积，sel[i]记录i这个体积是否可以达到，many[i]记录i这个体积至少需要多少种不同体积的桶来得到，tj[i]记录i这个体积所需桶集中最大的那个桶的编号，pre[i]记录i这个体积是通过哪个体积拓展到的。
初始化：sel[0]:=true;tj[0]:=-1;many[1..p]:=maxlongint;将v[i]排序。
主程序：外循环i枚举桶的编号，内循环j枚举体积，当体积已达到过时，对其向后连续拓展(k:=j+v[i],j+2*v[i]..直至超出p停止)，如果many[j]+1<many[k]那么更新。重要的:当many[j]+1=many[k]并且tj[j]<tj[pre[k]]时也要更新，这是为了保证集合的最优化。
对上述方程进行优化。设当前桶为i, 在k从小到大扫时维护min[L] = {j | (j mod v[i] = L) and （opt[j]最小 and 此时tj[j]尽可能小）and (j <= k)}。其实相当于v[i]个单调队列。这样对于k来说，必定从min[k mod v[i]]转移过来，实现O(1)转移。
故总复杂度为O(p * q + p log p)
有兴趣的可以看看Pascal程序
上述方法有问题吧。。。并不能保证字典序最优！比如同样两个等价类状态，个数是相同的，一个由v[3]、v[5]组成，一个由v[2]、v[6]组成，上述程序一定会出错的！
一个优化：读入时若存在v[i], v[j]使得v[i] mod v[j]=0, 则可删去v[i], 只保留v[j]--dementrock
{题解SKYWALKER_Q}
我比较傻……写的同余类优化的背包……本来想记录前驱来构造解，结果发现是错误的……在第8个点会Wa掉……然后改进后发现卡空间……于是我就傻了……改成先DP解决第一问，然后DFS搜索解，就AC了
Executing...
Test 1: TEST OK [0.000 secs, 4168 KB] Test 2: TEST OK [0.000 secs, 4168 KB] Test 3: TEST OK [0.000 secs, 4168 KB] Test 4: TEST OK [0.000 secs, 4168 KB] Test 5: TEST OK [0.000 secs, 4168 KB] Test 6: TEST OK [0.000 secs, 4168 KB] Test 7: TEST OK [0.032 secs, 4168 KB] Test 8: TEST OK [0.086 secs, 4168 KB] Test 9: TEST OK [0.022 secs, 4168 KB] Test 10: TEST OK [0.119 secs, 4168 KB]
IDFS， 判断解时用递推dp超时， 改bfs即秒过……
解析三的优化(不用单调队列):
仍然是Dp.但状态定义和转移方程可以改一下:
f[i,j] : 前i个桶装j夸脱的水,i不用时的最小值.
g[i,j] : 前i个桶装j夸脱的水,i使用时的最小值.
f[i,j]=min{f[i-1,j],g[i-1,j]};
g[i,j]=min{g[i,j-w[i]],min{f[i-1,j-w[i]],g[i-1,j-w[i]]}+1};
转移g[i,j]时g[i,j-w[i]]是用了多个第i个桶,后一项是只用了一个第i个桶,在阶段i总有一个j是分界点,用i-1转移,由此之后的g[i,j]都由g[i,j-w[i]]继承得到.输出方案时比较f[i,j]和g[i,j],f[i,j]<g[i,j]则不用i否则用i,当然用i时确定j需要找到那个分界点j0,由i,j----i,j0------i-1,j0-w[i] 转移到i-1.字典序的问题同解法三回溯比较.这样就优化掉了方程中的k,不需要剩余类和单调队列什么的.
BY：tangyan022
Executing...
Test 1: TEST OK [0.000 secs, 3340 KB] Test 2: TEST OK [0.000 secs, 3340 KB] Test 3: TEST OK [0.000 secs, 3340 KB] Test 4: TEST OK [0.000 secs, 3340 KB] Test 5: TEST OK [0.000 secs, 3340 KB] Test 6: TEST OK [0.000 secs, 3340 KB] Test 7: TEST OK [0.032 secs, 3340 KB] Test 8: TEST OK [0.032 secs, 3340 KB] Test 9: TEST OK [0.000 secs, 3340 KB] Test 10: TEST OK [0.022 secs, 3340 KB]
All tests OK.
先写一个DFS搜方案，再写一个DFS2判断该方案能否可行即可。
开始用DP判断解是否可行第十组数据TLE
注意到Q很大dp状态有20000，另外多组解肯定有重复的集合，这部分DP做了很多重复工作。
观察到题目的解是一个最小集合，因此答案桶的数量不会很大。
所以DFS判断解的速度要比DP快
一开始思路是求一元不定方程是否有整数解,WA一次后发现是正整数解 然后在枚举到最后完全背包过了,时间没有前面的同学快.但是思路特别简单...
第一个判断方法就是所有被选数的gcd能被Q整除,TEST7和10用了0.1s.....-leidar
