现在有一个订单:订单明细为:产品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)再加上??
请高手给个思路...

解决方案 »

  1.   

    只讨论分配好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的一次循环所被加的元素为一类,其对应的产品被打为一包。
      

  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;
    }
    }