[usaco]4.1.3 Fence Rails 多维背包问题,dfsid

简介: <p> Fence Rails<br> Burch, Kolstad, and Schrijvers <br> Farmer John is trying to erect a fence around part of his field. He has decided on the shape of the fence and has even already installed t

 Fence Rails
Burch, Kolstad, and Schrijvers
Farmer John is trying to erect a fence around part of his field. He has decided on the shape of the fence and has even already installed the posts, but he's having a problem with the rails. The local lumber store has dropped off boards of varying lengths; Farmer John must create as many of the rails he needs from the supplied boards.

Of course, Farmer John can cut the boards, so a 9 foot board can be cut into a 5 foot rail and a 4 foot rail (or three 3 foot rails, etc.). Farmer John has an `ideal saw', so ignore the `kerf' (distance lost during sawing); presume that perfect cuts can be made.

The lengths required for the rails might or might not include duplicates (e.g., a three foot rail and also another three foot rail might both be required). There is no need to manufacture more rails (or more of any kind of rail) than called for the list of required rails.

PROGRAM NAME: fence8
INPUT FORMAT
Line 1:  N (1 <= N <= 50), the number of boards 
Line 2..N+1:  N lines, each containing a single integer that represents the length of one supplied board 
Line N+2:  R (1 <= R <= 1023), the number of rails 
Line N+3..N+R+1:  R lines, each containing a single integer (1 <= ri <= 128) that represents the length of a single required fence rail 

SAMPLE INPUT (file fence8.in)
4
30
40
50
25
10
15
16
17
18
19
20
21
25
24
30

OUTPUT FORMAT
A single integer on a line that is the total number of fence rails that can be cut from the supplied boards. Of course, it might not be possible to cut all the possible rails from the given boards.
SAMPLE OUTPUT (file fence8.out)
7

HINTS (use them carefully!)
Fence Rails: Hint 1
This is a high dimensionality multiple knapsack problem, so we just have to test the cases. Given that the search space has a high out-degree, we will use depth first search with iterative deepening in order to limit the depth of the tree. However, straight DFSID will be too slow, so some tree-pruning is necessary.

---------------------------------------------------------
多维背包问题
使用dfs遍历,
首先把rails排序,然后,从最大的rail开始遍历。
对于第k个rail,遍历所有的板子,然后遍历地k-1个rail。如果所有的rail都有解法,则输出最开始rail。
usaco称之为DFSID

/*
ID:yunleis2
PROG:fence8
LANG:C++
*/


#include<iostream>
#include<fstream>

using namespace std;
const int MAXB=50;
const int MAXR=1024;
int boards[MAXB];
int remains[MAXB];
int rails[MAXR];
int b;
int r;
int board_sum=0;
int result=0;
int waste_max=0;
int from[MAXR];
fstream fout("fence8.out",ios::out);
inline void swap(int * a,int * b){
	int t=*a;
	*a=*b;
	*b=t;
//	*a=*a+*b;
//	*b=*a-*b;
//	*a=*a-*b;
}
int partiton(int * a,int p,int r)
{
	int x=a[r];
	int i=p-1;
	for(int j=p;j<r;j++){
		if(a[j]<x){
			++i;
			swap(a+j,a+i);
		}
	}
	swap(a+i+1,a+r);
	return i+1;
}
void quicksort(int * a,int p,int r)
{
	if(p<r)
	{
		int q=partiton(a,p,r);
		quicksort(a,p,q-1);
		quicksort(a,q+1,r);
	}
}
void dfs(int k,int waste){
	if(k<0){
		fout<<result+1<<endl;
		exit(0);
	}
	int i=0;
	if(k!=result&&rails[k]==rails[k+1])
		i=from[k+1];
	for(;i<b;i++){
		if(remains[i]>=rails[k]){
			from[k]=i;
			remains[i]-=rails[k];
			if(remains[i]<rails[0])waste+=remains[i];
			if(waste>waste_max){
				remains[i]+=rails[k];
				waste-=remains[i];
				continue;
			}
			dfs(k-1,waste);
			remains[i]+=rails[k];
		}
	}
}
int main()
{

	fstream fin("fence8.in",ios::in );
	fin>>b;
	for(int i=0;i<b;i++)
	{
		fin>>boards[i];
		board_sum+=boards[i];
		remains[i]=boards[i];
	}
	fin>>r;
	for(int i=0;i<r;i++)
		fin>>rails[i];
	quicksort(boards,0,b-1);
	quicksort(rails,0,r-1);
	int rail_sum=0;
	for(int i=0;i<r;i++){
		rail_sum+=rails[i];
		if(rail_sum>board_sum)
		{
			rail_sum-=rails[i];
			r=i;
			break;
		}
	}

	for(int i=r-1;i>=0;--i){
		result=i;
		waste_max = board_sum - rail_sum;
		rail_sum -= rails[i];
		dfs(i,0);
	}
	fout<<0<<endl;
	return 0;
}


目录
相关文章
|
弹性计算 应用服务中间件
2024年阿里云便宜服务器优惠合集:61元、99元、199元、165元、30元、26元
2024年阿里云便宜服务器优惠合集:61元、99元、199元、165元、30元、26元
4212 2
|
NoSQL JavaScript 前端开发
MongoDB系列--深入理解MongoDB聚合(Aggregation )
MongoDB中聚合(aggregate) 操作将来自多个document的value组合在一起,并通过对分组数据进行各种操作处理,并返回计算后的数据结果,主要用于处理数据(诸如统计平均值,求和等)。MongoDB提供三种方式去执行聚合操作:聚合管道(aggregation pipeline)、Map-Reduce函数以及单一的聚合命令(count、distinct、group)。
1842 0
MongoDB系列--深入理解MongoDB聚合(Aggregation )
|
机器学习/深度学习 SQL 分布式计算
Spark核心原理与应用场景解析:面试经验与必备知识点解析
本文深入探讨Spark核心原理(RDD、DAG、内存计算、容错机制)和生态系统(Spark SQL、MLlib、Streaming),并分析其在大规模数据处理、机器学习及实时流处理中的应用。通过代码示例展示DataFrame操作,帮助读者准备面试,同时强调结合个人经验、行业趋势和技术发展以展现全面的技术实力。
1323 0
|
算法 Unix Linux
linux线程调度策略
linux线程调度策略
295 0
|
12月前
|
SQL JavaScript 数据库连接
Seata的工作原理
【10月更文挑战第30天】
345 3
|
网络协议 安全 网络安全
常见的网络传输协议有几种
常见的网络传输协议涵盖多个层次,包括传输层(如TCP、UDP、SCTP)、应用层(如HTTP/HTTPS、FTP、SMTP、DNS、SSH)、网络层(如IP、ICMP、ARP)、数据链路层(如Ethernet、PPP、Wi-Fi)及安全协议(如SSL/TLS、IPSec)。这些协议各具特色,适用于不同场景,如TCP用于可靠传输,UDP适合实时应用,而HTTP/HTTPS则服务于网页浏览和数据交换。通过这些协议的协同工作,现代互联网和局域网得以实现多样化的应用和服务。
|
消息中间件 存储 RocketMQ
2分钟看懂RocketMQ延迟消息核心原理
本文从源码层面解析了RocketMQ延迟消息的实现原理,包括延迟消息的使用、Broker端处理机制以及定时任务对延迟消息的处理流程。
2分钟看懂RocketMQ延迟消息核心原理
|
应用服务中间件 Android开发
Server Tomcat v9.0 Server at localhost failed to start问题的解决
Server Tomcat v9.0 Server at localhost failed to start问题的解决
1214 0
|
弹性计算 大数据 测试技术
2024年阿里云服务器新购、续费、升级优惠信息整理汇总
随着云计算技术的深入普及,越来越多的企业和个人选择阿里云作为他们的云服务提供商。然而,续费成本往往成为用户考虑的重要因素。为了帮助用户更经济地续费,阿里云推出了一系列优惠活动和代金券。2024年阿里云服务器优惠活动,轻量2核2G3M服务器61元一年、2核4G4M带宽165元1年,云服务器4核16G10M带宽26元1个月、149元半年,阿里云ECS云服务器2核2G3M新老用户均可99元一年续费不涨价,企业用户2核4G5M带宽199元一年
3038 2
|
设计模式 算法 搜索推荐
从策略模式看软件设计的智慧-灵活应对变化的艺术
策略模式是一种行为设计模式,它定义了算法族,分别封装起来,让它们之间可以互相替换,使得算法的变化独立于使用算法的客户。本文深入探讨了策略模式的组成、应用场景、实现方式及其优缺点。通过实际案例,展示了策略模式在灵活处理算法和业务规则变化中的强大作用。文章还提供了最佳实践和使用注意事项,帮助开发者更有效地运用策略模式,同时比较了与其他设计模式的异同。掌握策略模式,将为您的软件设计带来更高的灵活性和可维护性。
628 0
从策略模式看软件设计的智慧-灵活应对变化的艺术