Algorithm

USACO Section5.3 Milk Measuring (milk4)

Problem Summary

Given the volume of the big bottle (Q) and the volumes of P pails (p[1],p[2],…,p[P]), which are all integers, find the minimal sets of pails Farmer John needs to buy in order to measure out Q quarts of milk.

Solution

This problem can be solved using DP, but it would be relatively hard to analysis and implement.

Instead, I used iterative deepening depth-first search (IDDFS). It is very easy to understand, and the coding is quiet simple, too.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <fstream>
using namespace std;
const int maxn = 102;
const int maxm = 20020;
int n,m,pail[maxn];
int ans;
bool avaliable[maxn];
int now[maxn],best[maxn];
void update(int new_ans)
{
	bool flag=false;
	if(ans<0)
	{
		ans=new_ans;
		flag=true;
	}
	if(!flag)
		for(int i=1;i<=ans;i++)
		{
			if(best[i]>now[i])
			{
				flag=true;
				break;
			}
			else
			if(best[i]<now[i])
				break;
		}
	if(flag)
		for(int i=1;i<=ans;i++)
			best[i]=now[i];
}
void dfs(int cur,int rest,int depth,int max_depth)
{
	if(depth>max_depth)
	{
		if(rest==0)
			update(max_depth);
		return;
	}
	if(cur>n || rest<pail[cur]) return;
	now[depth]=cur;
	for(int i=1;i<=rest/pail[cur];i++)
		dfs(cur+1,rest-i*pail[cur],depth+1,max_depth);
	dfs(cur+1,rest,depth,max_depth);
}
int main()
{
	fstream fin("milk4.in",ios::in);
	fstream fout("milk4.out",ios::out);
	fin>>m>>n;
	for(int i=1;i<=n;i++) fin>>pail[i];
	fin.close();
	for(int i=1;i<n;i++)
		for(int j=1;j<=n-i;j++)
			if(pail[j]>pail[j+1])
			{
				int tmp=pail[j];
				pail[j]=pail[j+1];
				pail[j+1]=tmp;
			}
	ans=-1;
	for(int lim=1;lim<=n;lim++)
	{
		dfs(1,m,1,lim);
		if(ans>0)
			break;
	}
	fout<<ans;
	for(int i=1;i<=ans;i++)
		fout<<" "<<pail[best[i]];
	fout<<endl;
	
	fout.close();
	return 0;
}