這道題要用到迭代加深搜索(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。對每個其他的桶的狀態可以直接由前面的狀態得出。

經過這個優化，數據就可以全過了。

<pre><span>USER: CmYkRgB123 CmYkRgB123 [cmykrgb1]
TASK: milk4
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 2864 KB]
   Test 2: TEST OK [0.011 secs, 2860 KB]
   Test 3: TEST OK [0.000 secs, 2864 KB]
   Test 4: TEST OK [0.000 secs, 2864 KB]
   Test 5: TEST OK [0.000 secs, 2864 KB]
   Test 6: TEST OK [0.000 secs, 2860 KB]
   Test 7: TEST OK [0.130 secs, 2860 KB]
   Test 8: TEST OK [0.032 secs, 2864 KB]
   Test 9: TEST OK [0.022 secs, 2860 KB]
   Test 10: TEST OK [0.194 secs, 2860 KB]

All tests OK.
</span>
<span>Your program ('milk4') produced all correct answers!  This is your
submission #3 for this problem.  <strong>Congratulations!</strong>
</span>
</pre>

/*
ID: cmykrgb1
PROG: milk4
LANG: C++
*/

#include <iostream>
#include <fstream>
#define MAXP 101
#define MAXQ 20001

using namespace std;

ifstream fi("milk4.in");
ofstream fo("milk4.out");

int Q,P,ans,v[MAXP],use[MAXP];

inline int cmp(const void * a,const void * b)
{
    return *(int *)a<*(int *)b?-1:1;
}

void init()
{
    int i;
    fi >> Q >> P;
    for (i=1;i<=P;i++) fi >> v[i];
    qsort(v+1,P,sizeof(v[0]),cmp);
}

void print()
{
    fo << ans;
    for (int i=1;i<=ans;i++) 
        fo << ' ' << v[ use[i] ];
    fo << endl;
    fi.close();    
    fo.close();    
    exit(0);
}

void judge()
{
    int i,j;
    bool f[MAXQ];
    memset(f,0,sizeof(f));
    for (i=1;i<=Q/v[use[1]];i++)
        f[ i*v[use[1]] ]=true;
    for (i=2;i<=ans;i++)
        for (j=v[use[i]];j<=Q;j++) //第一種牛奶桶至少用了一次
            f[j] |= f[ j- v[use[i]] ] ;
    if (f[Q]) 
        print();
}

void dfs(int k)
{
    int i,j;
    for (i=use[k-1]+1;i<=P-ans+k;i++)
    {
        use[k]=i;
        if (k==ans)    
            judge();
        else 
            dfs(k+1);
    }
}

void DFSID()
{
    for (ans=1;ans<=P;ans++)
        dfs(1);
}

int main()
{
    init();
    DFSID();
    return 0;
}