随笔-141  评论-9  文章-3  trackbacks-0
多维背包问题, 不能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 小阮 阅读(722) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理