This post is written in Chinese. Please consider using Google Translate

这道题要用到迭代加深搜索(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;
}