首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > JAVA > J2SE开发 >

100分只装箱单分配思路,高手们赐教

2012-03-23 
100分只求一个装箱单分配思路,高手们赐教!现在有一个订单:订单明细为:产品A330只、产品B175只、产品C110只、

100分只求一个装箱单分配思路,高手们赐教!
现在有一个订单:订单明细为:产品A 330只、
  产品B 175只、
  产品C 110只、
  产品D 45只、
  产品E 30只...

现在要把这些产品分配到一个个大的装箱中。每个装箱子可以放150只。以同类产品放到相同的箱子原则。
当第一先分配刚好可以150的后:产品A 2箱--------剩30只  
  产品B 1箱--------剩25只
  产品C 0箱--------剩110只
  产品D 0箱--------剩45只
  产品E 0箱--------剩30只...
第二:对剩下的产品排序,继续分配知道全部装完为止。 但是主要问题是:第步开始不知道如何组合为一个一个箱子。是C(110)+E(30)再加上??
请高手给个思路...

[解决办法]
只讨论分配好150的以后该如何分配的问题,算法很简单。

1 将各种产品按照剩余数量有多到少排列,排列后的顺序设为a[i],i={0,1,2,3,……}。
2 计算a[0]+a[1],如果<150,则计算a[0]+a[1]+a[2],以此类推;当N=a[0]+a[1]+...+a[n]<=150时,计算S=N+a[i]+a[i-1]+...+a[i-n];当S<=150时,去掉所有已经被加的元素,将其打包;将余下的元素按照步骤1排序,然后按照步骤2处理。以此类推。

步骤1和2的一次循环所被加的元素为一类,其对应的产品被打为一包。


[解决办法]
我写了个小程序,楼主有兴趣看一看。算法思路不是最优的,但能比较好的完成任务。
package com.houlei.zhuangxiang;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;

public class ZhuangXiang {

public static void main(String[] args) {
ZhuangXiang fb = new ZhuangXiang();
LinkedList roder = fb.CreateOrder();
ArrayList boxSet = fb.fixBox(roder, 150);
fb.printBoxSet(boxSet);
}

public LinkedList CreateOrder(){
LinkedList order = new LinkedList();
order.add(new Product("产品A",330));
order.add(new Product("产品B",175));
order.add(new Product("产品C",110));
order.add(new Product("产品D",45));
order.add(new Product("产品E",30));
return order;
}

public ArrayList fixBox(LinkedList order,int boxSize){
ArrayList boxSet = new ArrayList();
//第一,能装满的先装满。
Iterator iter = order.iterator();
while(iter.hasNext()){
Product p = (Product)iter.next();
for(int i=0;i<p.getNumber()/boxSize;){
Box box = BoxFactory.createBox();
box.add(new Product(p.getName(),boxSize));
boxSet.add(box);
p.setNumber(p.getNumber()-boxSize);
}
}
//第二,剩下的拼箱装。
Collections.sort(order);//按由大到小排序(Product类实现了Comparable接口)
while(!order.isEmpty()){
Box box = BoxFactory.createBox();
Product first = (Product)order.removeFirst();
box.add(first);
int count = first.getNumber();
Iterator itr = order.iterator();
while(itr.hasNext()){
Product p = (Product)itr.next();
int num =count+p.getNumber(); 
if(num<boxSize){//挑数量多的装,少的留到下一箱
itr.remove();
box.add(p);
count += p.getNumber();
}
}
boxSet.add(box);;
}
return boxSet;
}
public void printBoxSet(ArrayList boxSet){
Iterator iter = boxSet.iterator();
while(iter.hasNext()){
Box box = (Box)iter.next();
System.out.print("第"+box.getBoxNumber()+"箱:");
Iterator itr = box.iterator();
while(itr.hasNext()){
Product p = (Product)itr.next();
System.out.print("\t"+p.getName()+":"+p.getNumber()+"只");
}
System.out.println();
}
}
}
class BoxFactory{
private static int count=0;
public static Box createBox(){
count++;
return new Box(count);
}
public static int getOutput(){
return count;
}
}
class Box extends LinkedList{
private static final long serialVersionUID = 1L;
public Box(int number){
boxNumber = number;
}


private int boxNumber;
public int getBoxNumber() {
return boxNumber;
}
public void setBoxNumber(int boxNumber) {
this.boxNumber = boxNumber;
}
}
class Product implements java.lang.Comparable{
private String name;
private int number;
public Product(){}
public Product(String name,int number){
this.name=name;this.number=number;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getNumber() {
return number;
}
public void setNumber(int number) {
this.number = number;
}
public int compareTo(Object obj) {
if(obj instanceof Product){
Product p = (Product)obj;
if(p.getNumber()==this.number)return 0;
if(p.getNumber()>this.number)return 1;
}
return -1;
}
}
[解决办法]
第二步以后,从大到小排序,然后从两头开始挑,如果刚好有能装一箱的,则装一箱,如果没有,则把最大的装箱,最小的填满,然后把剩下的排序,再重复这个步骤。

热点排行