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

上次修改时间 2017-05-22