Algorithm

USACO Section6.4 Fence Rails (fence8)

Problem Summary

Given N boards and R rails and their lengths, find the maximal number of wanted rails that can be cut from the given boards.

Solution

This is a multiple knapsack problem. Due to the high dimensionality, the search tree is huge, which made me think about using IDDFS (iterative deepening depth first search with iterative deepening) to limit the depth.

Then I combined IDDFS with binary search to make the search faster. That is , instead of traversing through all possible numbers, I use binary search to find the maximal number, and for each middle number, use DFS to determine if it is achievable.

After this, the search is still huge work, so I found a few ways to prune the search tree:

  1. If a rail has greater length than all boards, then there is no need to consider it.

  2. The range of each rail’s length is from 1 to 128, but R can be at most 1023. So there can be many rails of the same length. For any two rails with the same length, we can cut them from boards of non-decreasing index.

  3. If there is a board of the same length of the rail, then cutting that rail from that board is optimal.

  4. If there is a way to cut k rails, there is a way to cut the k shortest rails, so we only consider the k shortest rails.

  5. We can stop searching if it finds a way to cut the largest set of shortest rails such that the sum of the lengths of the rails waiting is greater than the sum of the left board lengths.

Besides, the search can get even faster if we add some greedy algorithm. We can sort the boards by length, and do the same for the rails. And for each time we start searching, we search from the rail with greatest length and try to cut from the board with least length.

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int maxn = 52;
const int maxm = 1024;
int n,m,b[maxn],r[maxm];
int sum_b,sum[maxm];
bool dfs(int cur_b,int cur_r)
{
	if(cur_r<=0)
		return true;
	
	int s=0;
	for(int i=1;i<=n;i++)
		if(b[i]>=r[1])
			s+=b[i];
	if(s<sum[cur_r]) return false;
	int st=1;
	if(cur_r<m && r[cur_r]==r[cur_r+1])
		st=cur_b;
	bool tmp;
	for(int i=st;i<=n;i++)
		if(b[i]==r[cur_r])
		{
			b[i]=0;
			tmp=dfs(1,cur_r-1);
			b[i]=r[cur_r];
			return tmp;
		}
	for(int i=st;i<=n;i++)
		if(b[i]>=r[cur_r])
		{
			b[i]-=r[cur_r];
			tmp=dfs(i,cur_r-1);
			b[i]+=r[cur_r];
			if(tmp) return true;
		}
	return false;
}
int main()
{
	fstream fin("fence8.in",ios::in);
	fstream fout("fence8.out",ios::out);
	fin>>n;
	sum_b=0;
	for(int i=1;i<=n;i++)
	{
		fin>>b[i];
		sum_b+=b[i];
	}
	fin>>m;
	for(int i=1;i<=m;i++)
		fin>>r[i];
	/* bubble sort for b */
	int tmp;
	for(int i=1;i<n;i++)
		for(int j=1;j<=n-i;j++)
			if(b[j]>b[j+1])
			{
				tmp=b[j];
				b[j]=b[j+1];
				b[j+1]=tmp;
			}
	int idx=1;
	for(int i=1;i<=m;i++)
		if(r[i]<=b[n])
		{
			r[idx]=r[i];
			idx++;
		}
	m=idx-1;
	sort(r+1,r+m+1);
	for(int i=1;i<=m;i++)
	{
		sum[i]=sum[i-1]+r[i];
		if(sum[i]>sum_b)
		{
			m=i-1;
			break;
		}
	}
	int l=0,r=m,mid;
	while(l<r)
	{
		mid=((l+r)>>1)+1;
		if(dfs(1,mid))
			l=mid;
		else
			r=mid-1;
	}
	fout<<l<<endl;
	fin.close();
	fout.close();
	return 0;
}