基于交易计算最小账单金额的算法

Question

我需要用java开发一个程序，在那里我需要计算给定项目的最小账单。

每个项目的标准价格如下：洋葱-5卢比番茄-10卢比马铃薯- 2卢比

还有一个不同商品交易的列表。一件商品可以有多笔交易。

2个洋葱-7.5卢比
3个洋葱-10卢比

3个番茄-25卢比
5个番茄-45卢比

3个土豆-5卢比
4个土豆-6.5卢比

它可以拥有更多。因此，该方法需要以这样一种方式计算账单金额，即对于任何给定的数量（考虑到给定的交易），它都应该给出最低账单金额。

输入将采用以下格式。程序应计算要支付的最低金额：-

洋葱，番茄，洋葱，土豆，番茄，葱，洋葱

(4)onion -> (10+5)  
(2)tomato -> (10*2)  
(1)potato -> 2  
------------------
minimum bill -> 37

我有两个班，一个叫蔬菜&下的其他指定交易

public class Deal {
    private String code;
    private String quantity;
    private String price;
    //getters & setters         
}

public class Vegetable{
private String code;
private String name;
private String price;
//getters & setters 
}

Answer 1

我不会为你做所有的事情，但这就是这个算法的样子：

public int getPrice(int code)
{
    int price = getVegetableBasePrice(code);
    Iterator<Deal> it = deals.iterator();
    while(it.hasNext())
    {
        Deal next = it.next();
        if(next.getCode() == code)
        {
            price = Math.min(price, deal.getPrice());
        }
    }
    return price;
}

最好一次计算所有商品的所有价格，因为当你可以用线性时间实现这一点时，这会导致多项式时间的复杂性。这取决于你需要的算法有多好。

Answer 2

这确实是背包问题。只需将总数视为背包的体积，将1除以每件物品的价格即可。

示例：

（4） 洋葱->W=4
项目：
2个洋葱-7.5卢比->w=2，价值=1/7.5
3洋葱-10卢比->w=3，价值=1/10

注意：每个项目单独解决此问题。

顺便说一句，互联网上有很多这样的源代码，不过我建议你先试试自己。