救命！最优订单问题

Question

简单写了一下，楼主可以参考，呵呵
import java.util.*;public class Test{       static ArrayList prices = new ArrayList();
 
       public static void main(String args[])
       {
              int quality = 31;
              double totalCost = 0;              prices.add(new PriceUnit(0,1,10,1.95));
      prices.add(new PriceUnit(1,11,20,1.90));
      prices.add(new PriceUnit(2,11,20,1.98));
      prices.add(new PriceUnit(3,1,10,3.0));       while(quality!=0)
              {
PriceUnit current = getMinPrice(); 
if( quality > current.getMax())
                 {
                     quality = quality - current.getMax();
     totalCost += current.getMax()*current.getPrice();
                 }
else if(quality < current.getMin())
                 {
continue;
}
                else if(quality >=current.getMin() && quality <= current.getMax())
                {
totalCost+= quality * current.getPrice();
quality = 0;
}              }  System.out.println(totalCost);
       }
       public static PriceUnit getMinPrice()
       {
double min = ((PriceUnit)prices.get(0)).getPrice();
                int index = 0; for(int i=0;i<prices.size();i++)
                {
         PriceUnit temp = (PriceUnit)prices.get(i);
                    if(temp.getPrice()<min && temp.getStatus()==true)
                    {
                        min = temp.getPrice();
                        index = i;
                    }

                }
((PriceUnit)prices.get(index)).setStatus(false);
return (PriceUnit)prices.get(index);
       }}class PriceUnit
{
private int id, min, max;
        private double price;
        private boolean available = true;        public PriceUnit(int id, int min, int max, double price)
        {
this.id = id;
                this.min = min;
                this.max = max;
                this.price = price;
}        public int getId()
        { return id;} public int getMin()
        { return min;}        public int getMax()
        { return max;}        public double getPrice()
        { return price;}        public boolean getStatus()
        { return available;}        public void setStatus(boolean status)
        { available = status;}
         
}

Answer 1

多谢！但算法有问题
若给出数据0 1-10   6
1 11-20  6.1
2 12-21  10
3 9-12   10.5 quantity=11得出结果是60...

Answer 2

呵呵，怎么会无解呢，恩，可能我的解释有问题~
当quantity=11的时候，若要选最低成本，只能到供应商ID(1)那去买11个，11个超过了供应商ID(0)的供应范围(它最多只能提供10个),所以，就以上数据来说，只能有两种办法，一是到ID(1)那去买，一个是到ID(3)那去买，相比之下还是ID(1)便宜...

Answer 3

ID    范围  单价
------------------
0    1-10   1.95
1    11-20  1.90
2    11-20  1.98
3    1-10   3.0
4    1－10  1.90
5    11－20  2.90
-------------------
比如有个订单是30件货物
处理订单：
A:由一个供应商提供：
     只有一种可能，10×3（由上述例子看出只有3个供应商（5个里有3个提供10件货物）做比较，找出最便宜的）
B:由二个供应商提供：
     只有一种可能：10＋20（总共有3×3＝9种情况）
C:由三个供应商提供：
    只有一种可能：10＋10＋10（总共有一种情况）
D:由四个供应商提供：
    没有可能
E:由五个供应商提供：
    没有可能
     .
     .
     .
     .个人认为：
    主要在于分解订单（分成几个供应商供货），确定由1－n（n>=2）个供应商是个关键。其中n是关键中的关键。
   就题论题，比如上述例子。当订单是30件货物时，30÷10（所有供应商中提供最少货物的数量）＝3
在这里就可以判断在大类上的情况。由1，2，3个供应商提供货物的3大类情况，即粗略判断出n＝3。然后再分别计算3大类中的每个有多少种情况。希望对楼主您有帮助
至于代码实现嘛，现在我感觉问题已经清楚啦

Answer 4

这其实不就是一个统筹学的基本的求整数解的问题，求最小和的问题，建议用方程列出然后或者用线性代数或者用统筹的东东得出算法，用java写出来就好了

Answer 5

EdgarFrancis(Edgar)，大虾，能写出统筹算法吗？谢谢

Answer 6

我懒得自己写了，看了楼上的，我就直接在这个基础上添了点代码，你看看能不能行
（没管代码风格，很乱，而且没做优化，效率很低，只是给你一个能跑的原型）
import java.util.*;public class Test {
    private static final int CANCEL_TRY_NEXT = -1;
    static ArrayList prices = new ArrayList();
    static Stack opStack = new Stack();
    static int quantity = 31;
    static double totalCost = 0;    public static void main(String args[]) {        prices.add(new PriceUnit(0, 1, 10, 1.95));
        prices.add(new PriceUnit(1, 11, 20, 1.90));
        prices.add(new PriceUnit(2, 11, 20, 1.98));
        prices.add(new PriceUnit(3, 1, 10, 3.0));        while (quantity != 0) {            Operation op = new Operation();            PriceUnit current = getMinPrice();
            if (current == null) {
//                if (opStack.empty()) {
//                    System.out.println("Not found");
//                    System.exit(0);
//                }
                //push back
                op.id = CANCEL_TRY_NEXT;
                opStack.push(op);
                System.out.println("can not get PriceUnit: cancel");
            } else if (quantity > current.getMax()) {
                quantity = quantity - current.getMax();
                totalCost += current.getMax() * current.getPrice();                op.id = current.getId();
                op.quantity = current.getMax();
                op.price = current.getPrice();
                opStack.push(op);
                System.out.println("buy: price:" + op.price + " quantity:" + op.quantity);
            } else if (quantity < current.getMin()) {
                //push back
                current.setStatus(true);
                op.id = CANCEL_TRY_NEXT;
                opStack.push(op);
                System.out.println("can not buy enough quantity: cancel");
            } else if (quantity >= current.getMin() && quantity <= current.getMax()) {
                totalCost += quantity * current.getPrice();
                
                op.id = current.getId();
                op.quantity = quantity;
                op.price = current.getPrice();
                opStack.push(op);
                quantity = 0;
                System.out.println("buy: price:" + op.price + " quantity:" + op.quantity);
            }        }
        System.out.println("-------------------------------------------");
        System.out.println("totalCost=" + totalCost);
        System.out.println("Operations:");
        while (!opStack.empty()) {
            Operation op = (Operation) opStack.pop();
            System.out.println("buy : price:" + op.price + ", quantity:" + op.quantity);
        }    }
    private static boolean isSkipped(PriceUnit price, Operation lastOp) {
        if (lastOp == null) return false;
        if (price.getPrice() > lastOp.price) return false;
        return true;
    }
    public static PriceUnit getMinPrice() {
        boolean cancel = false;
        Operation lastOp = null;
        if (!opStack.empty()) {
            lastOp = (Operation) opStack.peek();
            if (lastOp.id == CANCEL_TRY_NEXT) {
                opStack.pop(); //skip the flag
                lastOp = (Operation) opStack.pop(); //cancel the last operation
                for (int j = 0; j < prices.size(); j++) {
                    PriceUnit temp = (PriceUnit) prices.get(j);
                    if (temp.getId() == lastOp.id) {
                        temp.setStatus(true);
                    }
                }
                cancel = true;
                quantity += lastOp.quantity;
                totalCost -= lastOp.price * lastOp.quantity;
            }
        }
        //double min = cancel ? lastOp.price : Double.MAX_VALUE;
        double min = Double.MAX_VALUE;
        int index = -1;        for (int i = 0; i < prices.size(); i++) {
            PriceUnit temp = (PriceUnit) prices.get(i);
            if (temp.getPrice() <= min && temp.getStatus() == true ) {
                if ((cancel && !isSkipped(temp, lastOp)) || !cancel) {
                    min = temp.getPrice();
                    index = i;
                }
            }        }
        if (index == -1) {
            return null;
        } else {
            ((PriceUnit) prices.get(index)).setStatus(false);
            return (PriceUnit) prices.get(index);
        }    }
}class Operation {
    public int id;
    public int quantity;
    public double price;
}class PriceUnit {
    private int id, min, max;
    private double price;
    private boolean available = true;    public PriceUnit(int id, int min, int max, double price) {
        this.id = id;
        this.min = min;
        this.max = max;
        this.price = price;
    }    public int getId() {return id;
    }    public int getMin() {return min;
    }    public int getMax() {return max;
    }    public double getPrice() {return price;
    }    public boolean getStatus() {return available;
    }    public void setStatus(boolean status) {available = status;
    }
}

Answer 7

测试过了，对某些数值不对，比如1~10之间，抛出java.util.EmptyStackException异常，可能是小bug，好难理解这个程序阿，栈的操作我已经忘了差不多了：）

Answer 8

确实还是问题...
就我给的例子没问题，但如果换一下（ID0和ID1的单价对调）
ID    范围  单价
------------------
0    1-10   1.90
1    11-20  1.95
2    11-20  1.98
3    1-10   3.0
-------------------
最便宜应该是 20*1.95+1.98*11=60.78
而您的程序结果是1.95*11+3*10+1.9*10=70.45...

Answer 9

我不是JAVA ，但我觉得问题应该是：
每次先价格进行从低到高排序，再对他们进行从你到高的顺序去求定单数。
ID    范围  单价
------------------
0    1-10   1.90
1    11-20  1.95
2    11-20  1.98
3    1-10   3.0
-------------------
比如要30。那就可以先得到1.9最低，取出最大数10
还差的就到第二位价上取，得到的是20的1.95
那么最低价应该是：1.9*10+1.95+20＝58
如果取的是10的就应该是：1.9*10＝19
如果是40的那就是：1.9*10+1.95*20+1.98*10＝77.8不知对不对？