本文正體字版由OpenCC轉換

這道題要用到迭代加深搜索(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