本文最先发表在本人的个人博客
http://www.lovestblog.cn
先把题目晒出来,这个题目不是很难,但是当时仅仅因为输出的问题折腾了我大半天,在ACM提供的运行环境中只有到最后才能把结果输出,不能在中途就把结果输出来,不然老师看见那红色的
Wrong Answer,对于ACMER来说这是最不想看到的结果了,我们最喜欢看到蓝色的
Accepted,呵呵,因为这样就说明你的程序通过了。
Description
一个工厂制造的产品形状都是长方体,它们的高度都是h,长和宽都相等,一共有六个型号,他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6。这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵,所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。
Input
输入文件包括几行,每一行代表一个订单。每个订单里的一行包括六个整数,中间用空格隔开,分别为1*1至6*6这六种产品的数量。输入文件将以6个0组成的一行结尾。
Output
除了输入的最后一行6个0以外,输入文件里每一行对应着输出文件的一行,每一行输出一个整数代表对应的订单所需的最小包裹数。
Sample Input
0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0
Sample Output
2
1
这就是题目了,这是北大ACM在线答题中的一道题目,看了下那通过率为38%(3875/10153),即总共提交了10153次,答案完全正确的是3875次,高人还是蛮多的,所以我一般选择的题目都是难度在百分之三十多左右的,太难的我不敢做,有兴趣的可以去网站上看看http://poj.grids.cn/problemlist,注册个用户答答题也蛮有意思的,但是只提供你有限的测试数据,当然当你提交的时候就不是几组测试数据了,难度还是比较高的,稍不留神就通不过。
对于这道题我最初这么思考的,对于6*6的一个箱子来说,最多只能放一个6*6或一个5*5或4*4的盒子,所以我们初始化需要的箱子数时就是这这几种箱子的个数和,对于3*3的箱子来说,我们可以放一个或2个或3个或4个,这我们可以通过整除和取模来确定放了3*3盒子的箱子数,再把它加入到总箱子数中,接下来我们就是把1*1和2*2的盒子塞进前面所需的箱子中,当塞不完时再来新增盒子,我们首先要将前面的箱子剩余的空间统计出来,并且要以2*2的优先考虑,因为我们可以把多余的2*2的位置变为填充4个1*1的,毕竟1*1的只要有空间随处都可以塞。所以当我们的箱子要是装了1个5*5的盒子的话,那么它就只能塞1*1的了,一个可以塞11个1*1的,对于装了4*4的盒子的话,那么还可以装5个2*2的盒子,暂且不要去转话成1*1的,除非没办法只能装1*1的,对于3*3的话就可以根据取模之后一个箱子剩下的空间了,如果一个箱子中只放了一个3*3的,那么还剩下3个3*3的空间可以放,我们知道可以放5个2*2的和7个1*1的,对于放了2个3*3的箱子,我们剩下的空间可以放3个2*2的以及6个1*1的,对于放了3个3*3的箱子,我们只能放1个2*2的和5个1*1的,这样一来我们就统计出了此时可以放2*2以及1*1的空间到底有多少,接下来我们就放箱子进去啊,放一个就减一个,知道1*1的和2*2的盒子都放完了,要是还没有放完的话我们就新增箱子或者如果1*1的没放完,而2*2的还有剩,那么就将每个2*2的转化成4个1*1的就行了,具体实现就看下面的代码吧,由于时间关系,就没写注释了,要是哪里看不明白的,可以给我留言。
import java.io.BufferedInputStream;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Test {
public static void main(String args[]){
Scanner sc=new Scanner(new BufferedInputStream(System.in));
boolean flag=true;
Map map=new HashMap();
int k=0;
while(flag){
int n[]=new int[6];
n[0]=sc.nextInt();
n[1]=sc.nextInt();
n[2]=sc.nextInt();
n[3]=sc.nextInt();
n[4]=sc.nextInt();
n[5]=sc.nextInt();
if(n[0]==0&&n[1]==0&&n[2]==0&&n[3]==0&&n[4]==0&&n[5]==0){
flag=false;
}else{
map.put(k, n);
k++;
}
}
for(int i=0;i<map.size();i++){
int[] vs=(int[])map.get(i);
int boxNum=0;
boxNum+=vs[3]+vs[4]+vs[5];
if(vs[2]>0){
if(vs[2]%4==0){
boxNum+=vs[2]/4;
}else{
boxNum+=vs[2]/4+1;
}
}
int for1=vs[4]*11;
int for2=vs[3]*5;
if(vs[2]%4==1){
for1+=7;
for2+=5;
}else if(vs[2]%4==2){
for1+=6;
for2+=3;
}else if(vs[2]%4==3){
for1+=5;
for2+=1;
}
if(vs[0]<for1){
vs[0]=0;
}else{
vs[0]=vs[0]-for1;
}
if(vs[1]<for2){
if(vs[0]>0){
if(4*(for2-vs[1])-vs[0]>=0){
vs[0]=0;
}else{
vs[0]=vs[0]-4*(for2-vs[1]);
}
}
vs[1]=0;
}else{
vs[1]=vs[1]-for2;
}
if(!(vs[0]==0&&vs[1]==0)){
if(vs[1]>0){
if(vs[1]%9==0){
boxNum+=vs[1]/9;
}else{
boxNum+=vs[1]/9+1;
if(vs[0]>(9-(vs[1]%9))*4){
if((vs[0]-(9-(vs[1]%9))*4)%36==0){
boxNum+=(vs[0]-(9-(vs[1]%9))*4)/36;
}else{
boxNum+=(vs[0]-(9-(vs[1]%9))*4)/36+1;
}
}
}
}else if(vs[0]>0){
if(vs[0]%36==0){
boxNum+=vs[0]/36;
}else{
boxNum+=vs[0]/36+1;
}
}
}
System.out.println(boxNum);
}
}
}
分享到:
相关推荐
实验2装箱问题-贪心算法 在本实验中,我们将学习贪心算法的设计和实现,以解决装箱问题。贪心算法是一种常用的近似算法,通过选择当前最优解来逐步构建解决方案。 问题描述 装箱问题是计算机科学中的一类经典问题...
数学建模装箱问题PPT学习教案 数学建模装箱问题是一种经典的组合优化问题,它有广泛的应用,在日常生活中也屡见不鲜。装箱问题是指寻找一种方法,使得能以最小数量的箱子数将物品装入箱内。 装箱问题的描述: 设...
贪心算法的思想---集装箱的装箱问题(c语言算法)
综合遗传和退火的混合算法解决三维装箱问题,仅部分代码
利用遗传算法解决一维装箱问题,并利用matlab实现
利用遗传算法和模拟退火,解决三维装箱问题,并可图形化展示装箱方案结果
三维装箱问题MATLAB代码,注释比较少,需要学习的可以下载。
三维装箱问题的MATLAB可视化仿真最后输出三维装箱效果,matlab2021a测试。仿真速度较慢。
【三维装箱】基于粒子群算法求解三维装箱问题matlab源码.md
作为三维装箱问题的一种工程应用,集装箱装载问题(Container Loading Problem,CLP)通常是指如何将一些小尺寸货物按照某种方式装入集装箱中。集装 箱装载质量的好坏,直接影响着企业运输成本的高低。如何给出一个...
装箱问题 【问题描述】 有一个箱子容量为V(正整数,0),同时有n 个物品(0),每个物 品有一个体积(正整数)。要求从m 个物品中,任取若干个装入箱内,使箱子的剩余空间为 最小。 【输入文件】 第1 行两个整数v 和...
【摘要】装箱问题属于典型的NP完全问题,旨在充分考虑容器承重、容积等因素的前提下,对装箱问题通过数学建模与算法实现来提高空间利用率,从而实现利润最大化。本文主要
matlab二维装箱问题求解
可以模拟装箱问题,利用画矩形框的形式,使得装箱问题更加直观。
事实上,集装箱的装箱问题在大部分企业中一直得不到很好解决,往往是凭经验作业,造成: • 空间利用率低,平均只有八成左右 • 计算耗时费力,难以得到优化方案 • 货物装柜超重,装载数量不准确 • 作业缺乏...
装箱问题,内有说明,应用贪心算法,进行从大到小的分配到包装箱
算法思想: 本实验采用贪心算法的思想。将集装箱想象成为一个长为L、宽为W、高为H的长方体,将圆柱形木材想象成为一底面半径为ri、长为L的圆柱体。 1、首先需要对圆柱体按半径从大到小进行排序,排完序后将其分为...
对于背包问题和装箱问题,都可以采用组合的思路进行求解。本题目给出了具体的求解思路和C++实验代码。以及正确的实验结构,对于求解背包问题有很大的实际意义。
货物配装问题实质上是背包问题与装箱问题的混合,有着广泛的应用。配装,是指充分利用运输工具(如火车、货车、轮船等,本文主要是指货车) 的载重量和容积,采用先进的装载方法,合理安排货物的装载计划,最大限度地发挥...