java - 如何避免在递归中重复检查？

Question

很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的，无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它， visit the help center 。

已关闭 10 年前。

对于那些已经阅读过我上一篇文章的人，我确实有一个不同的解决方案。请不要走开。

这是学校的作业问题(抱歉说得太长了，我已经尝试缩短它了)

我倾向于根据我身上有多少钱来点餐。无论服务如何，我都喜欢至少给 15% 小费(我已经在任何给定的一周内对表现进行了充分的评估)，而且我讨厌给钱的整个过程，等待女服务员回来找零钱，试图找到正确的小费改变以做出适当的小费。我所做的就是检查菜单，寻找最适合我身上的钱的食物组合。当我说最佳匹配时，我的意思是最接近 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 的资金输入需要太长时间。我尝试添加 boolean 列表“花了"来指示哪些已经被选中，但它根本不起作用，让我很困惑:(

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

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

Answer 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。

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

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

我还为最佳情况创建了类变量:

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 + "%");