救命！最优订单问题
问题是这样的
供货商提供n条供货单分别含数量范围和单价，如何从n个供货单中取单下单使得成本最低，例子如下
假设这里n=4,即有4条供货单(已经按单价排序）
ID 范围 单价
------------------
0 1-10 1.95
1 11-20 1.90
2 11-20 1.98
3 1-10 3.0
-------------------
现在需要下31个货物的订单，应该如何从以上供货单中抽取使其成本最低，例如上面的例子我们可以取
id(1) 20个
id(2) 11个
成本为20*1.90+11*1.98=59.45最便宜
如何用程序实现？急啊，拜托各位~
问题点数：0、回复次数：31Top
1 楼milkbottle（奶瓶->好好学习，天天向上）回复于 2005-04-02 10:24:49 得分 0
简单写了一下，楼主可以参考，呵呵
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;}
}Top
2 楼jmlinlin（天堂射手）回复于 2005-04-02 18:32:55 得分 0
多谢！但算法有问题
若给出数据
0 1-10 6
1 11-20 6.1
2 12-21 10
3 9-12 10.5
quantity=11得出结果是60...Top
3 楼milkbottle（奶瓶->好好学习，天天向上）回复于 2005-04-02 19:04:45 得分 0
汗... 你给出的数据是无解的啊
当然算不对了....
Top
4 楼jmlinlin（天堂射手）回复于 2005-04-02 20:03:10 得分 0
呵呵，怎么会无解呢，恩，可能我的解释有问题~
当quantity=11的时候，若要选最低成本，只能到供应商ID(1)那去买11个，11个超过了供应商ID(0)的供应范围(它最多只能提供10个),所以，就以上数据来说，只能有两种办法，一是到ID(1)那去买，一个是到ID(3)那去买，相比之下还是ID(1)便宜...Top
5 楼007remember（绿原）回复于 2005-04-02 20:03:41 得分 0
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大类中的每个有多少种情况。
希望对楼主您有帮助
至于代码实现嘛，现在我感觉问题已经清楚啦
Top
6 楼milkbottle（奶瓶->好好学习，天天向上）回复于 2005-04-02 20:44:30 得分 0
哦哦， 是我理解错了，呵呵
再改改Top
7 楼jmlinlin（天堂射手）回复于 2005-04-02 20:47:38 得分 0
多谢帮忙~HOHOTop
8 楼simonxuluo（爱江山更爱美人）回复于 2005-04-02 21:07:01 得分 0
还是不明白题意，题目好像是一个供应商提供供货单，就我表面理解就是先找最便宜的开始吧Top
9 楼EdgarFrancis（Edgar）回复于 2005-04-02 21:42:03 得分 0
这其实不就是一个统筹学的基本的求整数解的问题，求最小和的问题，建议用方程列出然后或者用线性代数或者用统筹的东东得出算法，用java写出来就好了Top
10 楼simonxuluo（爱江山更爱美人）回复于 2005-04-02 21:52:06 得分 0
EdgarFrancis(Edgar)，大虾，能写出统筹算法吗？谢谢Top
11 楼jmlinlin（天堂射手）回复于 2005-04-02 21:54:50 得分 0
问题是忘光了...你能给出个模型么Top
12 楼DanielYWoo（绿色毒汁）回复于 2005-04-02 22:07:27 得分 0
我懒得自己写了，看了楼上的，我就直接在这个基础上添了点代码，你看看能不能行
（没管代码风格，很乱，而且没做优化，效率很低，只是给你一个能跑的原型）
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;
}
}
Top
13 楼DanielYWoo（绿色毒汁）回复于 2005-04-02 22:09:48 得分 0
我没怎么多想，我大致觉得应该是从最便宜的买，买到后面数量不足，那就倒回去，尝试贵一点的.....
一直下去，就应该可以了，没多想，可能有问题，楼主您多试试那个程序Top
14 楼simonxuluo（爱江山更爱美人）回复于 2005-04-02 22:38:16 得分 0
测试过了，对某些数值不对，比如1~10之间，抛出java.util.EmptyStackException异常，可能是小bug，好难理解这个程序阿，栈的操作我已经忘了差不多了：）Top
15 楼jmlinlin（天堂射手）回复于 2005-04-02 22:48:59 得分 0
确实还是问题...
就我给的例子没问题，但如果换一下（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
...Top
16 楼simonxuluo（爱江山更爱美人）回复于 2005-04-02 23:12:01 得分 0
这个题是否请人工智能大师来讨论一下？Top
17 楼007remember（绿原）回复于 2005-04-02 23:35:37 得分 0
学习ingTop
18 楼jmlinlin（天堂射手）回复于 2005-04-03 01:06:32 得分 0
没人有想法了么，呵呵自己顶一下
Top
19 楼jmlinlin（天堂射手）回复于 2005-04-03 16:45:30 得分 0
没人了...Top
20 楼Mlfeng（枫叶染红）回复于 2005-04-03 17:23:36 得分 0
我不是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
不知对不对？Top
21 楼jmlinlin（天堂射手）回复于 2005-04-03 18:34:16 得分 0
这是最简单的办法，也是麻烦最多的事情，比如你考虑11个的话，这个方法就不是最优的了
10*1.90+1*3.0>11*1.95
Top
22 楼Mlfeng（枫叶染红）回复于 2005-04-03 19:47:35 得分 0
11应该就是 1.90*10+1.95*1当然小于11*1.95
是按价格排序,不是数量Top
23 楼jmlinlin（天堂射手）回复于 2005-04-03 20:53:39 得分 0
恩，你可能误会题意了，请仔细看一下，11表示ID1只提供11-20个，他不提供1-10个的，请仔细看Top
24 楼jmlinlin（天堂射手）回复于 2005-04-03 20:57:32 得分 0
再解释一下,订单需要11个货物，供应商人提供的供或单为
ID 范围 单价
------------------
0 1-10 1.90
1 11-20 1.95
2 11-20 1.98
3 1-10 3.0
-------------------
已经按价格排序，范围表示供货商只提供该范围内数量的货物Top
25 楼winstarr（星仁）回复于 2005-04-03 21:16:55 得分 0
upTop
26 楼freshbig（智猪）回复于 2005-04-03 21:29:23 得分 0
这是一个背包问题
Top
27 楼qiongtumlL（海上孤魂）回复于 2005-04-03 21:46:52 得分 0
这个东西应该考虑模拟退火算法Top
28 楼DanielYWoo（绿色毒汁）回复于 2005-04-04 11:54:27 得分 0
呵呵，我改写的那个是贪婪法吧，那个应该是不能得最优解的，只是近似解。可能应该用动态规划，帮你顶一下Top
29 楼007remember（绿原）回复于 2005-04-04 12:41:06 得分 0
学习ing
帮您顶Top
30 楼vssivl（克斯）回复于 2005-04-04 16:14:28 得分 0
楼主题目给的不完全，如果给定31个，那应该从0到31的标价都给出来，比如
------------------
0 1-10 1.95
11-40 1.80
1 11-20 1.90
21-40 1.81
2 11-20 1.98
21-40 1.82
3 1-10 3.0
11-25 2.8
26-40 2.7
-------------------
楼主给的条件实际上适用于给定总价格求可买的最多个数。
Top
31 楼jmlinlin（天堂射手）回复于 2005-04-06 10:49:39 得分 0
恩，差不多是这个意思，也可以说给定数量挑最优组合，唉，东西已经交出去了，参考了贪婪和背包的问题，看了有点晕了...Top
