多维背包问题, 不能DP, 由于搜索树又宽又深, 所以可以采取DFSID.
1. 对board、rail排序。并计算sum_board。对于每个rail，小的肯定比大的容易得到，取前k个rail的和 sum_rail，
使得 sum_rail < sum_board && sum_rail + rail[k] > sum_board
2. 从大到小枚举rail时，设from数组，保存每个rail是从哪个board来的，由于rail 肯定有重复，当rail[k] == rail[k+1]时候， 第k个rail的from值肯定是大于等于第k+1个rail来自的from，最少是from[k] = from[k+1];
3.设一个浪费值waste, n个rail之和sum_rail* （区别sum_rail)， 则最多只能浪费 sum_board - sum_rail* 这么多木材，因为如果浪费更多的话，则剩余board肯定不够切
参考了USACO上边好多代码。。。
/**//*
ID: lorelei3
TASK: fence8
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55;
const int R = 1024;
bool flag;
int board[N], remain[N], from[N], rail[R];
int sum_board, sum_rail, max_waste, n, r,ans;
ifstream fin;
ofstream fout;
void dfs(int k, int waste)
{
if(k<0){
flag =true;
fout<<ans+1<<endl;
exit(0);
}else{
int i;
if(k!= ans && rail[k] == rail[k+1])
i = from[k+1];
else
i=0;
for( ; i<n; ++i)
if(remain[i]>=rail[k]){
from[k] = i;
remain[i] -= rail[k];
if(remain[i] < rail[0]) waste += remain[i];
if(waste > max_waste){
waste -= remain[i];
remain[i] += rail[k];
continue;
}
dfs(k-1, waste);
remain[i] += rail[k];
}
}
}
int main(){
flag =false;
int i, nrail;
fin.open("fence8.in");
fout.open("fence8.out");
fin>>n;
for(i=0; i<n; ++i){
fin>>board[i];
remain[i] = board[i];
sum_board += board[i];
}
fin>>r;
for(i=0; i<r; ++i)
fin>>rail[i];
sort(board, board+n);
sort(rail, rail+r);
for(i=0; i<r; ++i){
if(sum_rail+rail[i]>sum_board)
break;
sum_rail+=rail[i];
}
nrail = i;
for(i= nrail-1; i>=0; --i){
ans = i;
max_waste = sum_board - sum_rail;
sum_rail -= rail[i];
dfs(i, 0);
}
if(!flag)
fout<<0<<endl;
return 0;
}
posted on 2011-01-22 01:22
小阮 阅读(731)
评论(0) 编辑 收藏 引用 所属分类:
USACO