0

对于那些已经阅读了我上一篇文章的人，我对此有不同的解决方案。请不要只是走开。

这是学校的作业问题（对不起，长篇大论，我已经尝试缩短它）

我倾向于根据我身上有多少钱来订购食物。无论服务如何，我都喜欢至少给 15% 的小费（我已经对任何一周的表现进行了足够的评估）而且我讨厌给钱的整个过程，等待女服务员带着零钱回来试图找到正确的更改以做出适当的提示。我所做的是检查菜单上最适合我的钱的食物组合。当我说最佳匹配时，我的意思是最接近 15% 而不会下降，而且我只选择每种食物一次。正如你可以想象的那样，我需要一些时间来计算所有这些，所以我希望你制作一个我可以使用的方法。

该方法仅适用于以下菜单：

Bandera Pizza Bread 6.49
Boston's Pizza Bread    5.35
Garlic Twist Bread  7.49
Single Order    5.35
Sun-Dried Tomato Bruschetta 6.99
Three Cheese Toast  6.35
Double Order wings  16.49 
Starter Size wings  8.99 
Cactus Nachos   10.29
Baked Ravioli Bites 8.49
Southwest Quesadilla    9.25

创建一个名为 selectFood 的方法，它将我拥有的金额作为参数，在屏幕上输出选择并返回我将保留的百分比小费，四舍五入到小数点后一位。如果食物多于两个人，请不要担心，我经常和大群人一起出去。

一些示例输出：

Best order for $10.00 is:Baked Ravioli Bites
The tip is 17.79%

Best order for $20.00 is:Sun-Dried Tomato Bruschetta, Cactus Nachos
The tip is 15.74%

Best order for $60.00 is:Bandera Pizza Bread, Boston's Pizza Bread, Three Cheese Toast, Double Order wings, Starter Size wings, Baked Ravioli Bites
The tip is 15.03%

Best order for $190.00 is:Bandera Pizza Bread, Boston's Pizza Bread, Garlic Twist Bread, Single Order, Sun-Dried Tomato Bruschetta, Three Cheese Toast, Double Order wings, Starter Size wings, Cactus Nachos, Baked Ravioli Bites, Southwest Quesadilla
The tip is 107.58%

我的老师有一个限制——我们不允许使用数组列表。

这是我最新的尝试：

import java.util.*;

class MethodAssign7{
    public static void main(String[]args){
        boolean[] took = {false,false,false,false,false,false,false,false,false,false,false};
        double money = 70.0;
        //System.out.println(selectFood(money/1.15,took));
        selectFood(money,took);
        System.out.println(closest/money*100+15);
    }
    static double closest = 10000.0;
    static void selectFood(double money, boolean[] took){
        String[] food = {"Bandera Pizza Bread","Boston's Pizza Bread","Garlic Twist Bread","Single Order","Sun-Dried Tomato Bruschetta","Three Cheese Toast","Double Order wings","Starter Size wings","Cactus Nachos","Baked Ravioli Bites","Southwest Quesadilla"};
        double[] costs = {6.49,5.35,7.49,5.35,6.99,6.35,16.49,8.99,10.29,8.49,9.25};

        if(money<5.35){
            if(money<closest){
                closest = money;
            }
        }
        else{
            for(double d: costs){
                if(money-d*1.15>0){
                    //System.out.println(money-d);
                    selectFood(money-d*1.15,took);
                }
            }
        }
    }
    /*static void printSelections(double money, boolean[] took){
        String[] food = {"Bandera Pizza Bread","Boston's Pizza Bread","Garlic Twist Bread","Single Order","Sun-Dried Tomato Bruschetta","Three Cheese Toast","Double Order wings","Starter Size wings","Cactus Nachos","Baked Ravioli Bites","Southwest Quesadilla"};
        double[] costs = {6.49,5.35,7.49,5.35,6.99,6.35,16.49,8.99,10.29,8.49,9.25};

        if(money<5.35){
            if(money==closest){
                print the choices by using took
            }
        }
        else{
            for(int i=0;i<costs.length;i++){
                if(money-costs[i]*1.15>0 && took[i]!=true){
                    took[i]=true;
                    //System.out.println(money-d);
                    selectFood(money-costs[i]*1.15,took);
                }
            }
        }
    }*/
}

我试图先用动态编程解决问题的百分比部分，我可以用我的程序得到百分比答案，但是输入 60 以上的钱需要很长时间。我试图添加布尔列表“took”来表示哪些已经被选中，但它根本不起作用，让我感到困惑:(

所有被注释掉的部分都是为了输出食物的选择。而且我知道我的 selectFood 方法现在只是 void 并且不会返回值，但我认为这更容易修复。我现在只关心如何让这个百分比部分起作用。

感谢您花时间阅读我的问题，如果您能帮助我，我将不胜感激，或者如果您不明白我的要求，请发表评论告诉我。

4

1 回答 1

1

最简单的版本是你从一笔钱开始，x。至少需要一定数量的小费作为小费，我们将其称为 t。这实际上意味着你想花尽可能多的钱，而不会超过 (x - t)。

那么你想要做的是定义你的目标：

    double totalMoney = 190.0;
    double minimumTip = totalMoney/115*15;
    double targetMoney = totalMoney - minimumTip;

我将假设您具有所需的数据结构，如下所示：

    MenuItem[] items = new MenuItem[]
    {
        new MenuItem("Bandera Pizza Bread", 6.49),
        new MenuItem("Boston's Pizza Bread", 5.35),
        [...]
    };

现在我们要递归搜索这些项目的最佳可能组合，以使所选项目的总成本最大化，同时始终保持小于 targetMoney。

递归树的每个分支将代表我可以购买的一种产品组合。这是我的解决方案和您的解决方案之间的主要区别。在树的第一个分支上，我将评估两种可能性——要么我会购买“Bandera Pizza Bread”，要么我不会。在二级分店，我会评估是否应该购买“波士顿披萨面包”。在每次递归调用中，我只需要知道我是否还有钱可花（此时我会查看列表中的下一项）或者该订单是否“超支”，此时我放弃了组合（因为购买其他任何东西只会让它变得更加昂贵！）。

为了减少我需要创建/丢弃的数组数量，我使用一个整数“selected”作为一个位字段，指定我决定在这个分支上购买哪些项目。如果位为 1，则我选择购买此商品。如果位为 0，则我选择不购买此商品。您可以使用布尔数组获得相同的效果，但是会有很多数组操作妨碍我演示的实际算法。

我还为最好的情况创建了类变量：

int    bestPurchaseSet = 0;
double bestCost = 0;

您不必这样做，您可以使用参数和返回类型传递结果，但这样可以减少代码的繁重。

那么，递归函数看起来有点像这样：

public void search(MenuItem[] items,
                   int        selected,
                   int        depth,
                   double     currentCost,
                   double     maxCost)
{
    if(currentCost > maxCost)
    {
        // too expensive
        return;
    }

    if(currentCost > bestCost)
    {
        // New best combination! Save it.
        bestCost = currentCost;
        bestPurchaseSet = selected;
    }

    if(depth >= items.length)
    {
        // run out of food types
        return;
    }

    // if we do choose this item, then we mark it as selected and increase the cost of this order.
    search(items, selected | (0x1 << depth), depth + 1, currentCost + items[depth].cost, maxCost);

    // if we don't choose this item
    search(items, selected, depth + 1, currentCost, maxCost);
}

这应该非常有效地运行，因为每个食物项只会增加一个额外的递归级别 - 并且许多递归分支被提前切断（一旦购买变得太昂贵）。

最后，打印出结果：

    System.out.print("Best order for $" + totalMoney + " is: ");
    for(int i=0; i<items.length; i++)
    {
        if((bestPurchaseSet & (0x1 << i)) != 0)
        {
            System.out.print(items[i].name + ", ");
        }
    }

    System.out.println("The tip is " + (totalMoney - bestCost)/bestCost * 100 + "%");
于 2012-10-19T06:46:46.193 回答