[递归回溯枚举] 装载问题

装载问题

题目描述

有一批共?n?个集装箱要装上 2 艘载重量分别为?c1和?c2的轮船，其中集装箱?i?的重量为?wi，且

装载问题要求确定，是否有一个合理的装在方案可将这?n?个集装箱装上这 2 艘轮船。如果有，找出最优装载方案。

关于输入

输入要输入
1、集装箱数量 类型整型
2、集装箱重量数组 类型整型数组
3、两艘轮船的载重量 类型整型数组
输入格式如：
5
67 34 2 69 24
78 158

关于输出

如果能装载的话输出格式如下：
ok,can load it
a way is:
the first trip load:2 69
the second trip load:67 34 24
如果不能装载的话输出如下：
can't find a way to Loading

例子输入

5
67 34 2 69 24
78 158

例子输出

ok,can load it
a way is:
the first trip load:2 69
the second trip load:67 34 24

提示信息

100% 测试数据保证n<=25。最优装载问题采用算法：尽量将第一艘轮船装满，然后将剩余的集装箱装到第二艘轮船上。

解题分析

尽量将第一个集装箱装满是为了保证我们尽可能地多利用第一个集装箱，而不造成容量的浪费。显然，我们可以用一个bool类型的数组，利用递归回溯的方法，用0表示不取该物品，用1表示取该物品，不断地去枚举所有可能的情况，并且，适当地做出减枝的操作，就是说我们判断一下当前第一艘船的容量能不能装下该物品，如果不能的话就不考虑装下该物品的情况了。当我们枚举完全部的情况后，我们去判断剩下的物品能不能被第二艘船装下，如果能就说明这是一种可行的方案，并且我们输出这个方案。

使用深度优先搜索（DFS）算法来解决最优装载问题。

程序首先读取输入，包括集装箱数量n、集装箱重量数组w[]和两艘轮船的载重量数组c1和c2。然后，定义一个全局变量wc1来记录尽量装满第一艘轮船时的重量，并定义两个布尔型数组w1[]和ans[]，分别记录装载方案和最优装载方案。

然后，程序进入dfs()函数，dfs()函数用于遍历所有可能的装载方案。它的参数有step和content，其中step表示当前遍历到的集装箱序号，content表示当前第一艘轮船的剩余载重量。

如果step等于集装箱数量n+1，表示已经遍历完所有集装箱，此时判断当前装载的重量是否小于wc1，如果小于，将当前装载重量作为wc1，并将当前装载方案记录在ans[]数组中。

如果step不等于集装箱数量n+1，表示还没有遍历完所有集装箱，则遍历所有的可能情况。将集装箱放入第一艘轮船（w1[step]=1）或不放入第一艘轮船（w1[step]=0），然后递归调用dfs()函数，更新step为step+1，更新content为content减去当前集装箱的重量（w[step]），继续遍历下一个集装箱。

最后，主函数根据最优装载方案ans[]的内容，判断是否存在合理的装载方案。如果第一艘轮船的重量小于等于c1，且第二艘轮船的重量小于等于c2，则存在合理的装载方案。程序输出"ok,can load it"表示存在装载方案，并输出该方案的具体内容。如果不存在合理的装载方案，则输出"can't find a way to Loading"。

需要注意的是，程序将两艘轮船的载重量分别存在c1和c2中，但在判断最优装载方案时，使用的是第二艘轮船的剩余载重量sumc2。当sumc2小于等于c2时，表示第二艘轮船可以装载集装箱，否则表示第二艘轮船无法装载所有集装箱。

代码实现

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

int n,w[1000],c1,c2;
int wc1=1e9;
bool w1[1000];
bool ans[1000];

void dfs(int step,int content){
	if(step==n+1){
		if(content<wc1){
			wc1=content;
			for(int i=1;i<=n;i++){
			    ans[i]=w1[i];
			}
		}
		return;
	}
	for(int i=0;i<2;i++){
		if(i==0 && w[step]<=content){
			w1[step]=1;
			dfs(step+1,content-w[step]);
		}
		else{
		    w1[step]=0;
			dfs(step+1,content);
		}
	}
}

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
	}
	scanf("%d%d",&c1,&c2);
	dfs(1,c1);
	int sumc2=0;
	for(int i=1;i<=n;i++){
	    if(ans[i]==0){
	        sumc2+=w[i];
	    }
	}
	if(sumc2<=c2){
	    printf("ok,can load it\na way is:\nthe first trip load:");
	    int flag=0;
	    for(int i=1;i<=n;i++){
	        if(flag==0 && ans[i]==1){
	            printf("%d",w[i]);
	            flag=1;
	        }
	        else if(ans[i]==1){
	            printf(" %d",w[i]);
	        }
	    }
	    printf("\nthe second trip load:");
	    flag=0;
	    for(int i=1;i<=n;i++){
	        if(flag==0 && ans[i]==0){
	            printf("%d",w[i]);
	            flag=1;
	        }
	        else if(ans[i]==0){
	            printf(" %d",w[i]);
	        }
	    }
	    printf("\n");
	}
	else{
	    printf("can't find a way to Loading\n");
	}
	return 0;
}

现