java不知道如何从给定菜单中找到低于目标值的最大价格

Question

我正在尝试创建一个名为selectFood的方法，该方法将我的钱数作为参数，在屏幕上输出选择，并返回我将保留的百分比提示，四舍五入到小数点后一位

我有可能的成本没有提示通过递归完成，但我需要比较它们，并找到更大的一个。请帮忙

public static void selectFood(double money){
    /*String[]menu={"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[]itemCost={6.49,5.35,7.49,5.35,6.99,6.35,16.49,8.99,10.29,8.49,9.25};

    possibilities(itemCost.length,"",itemCost,money);

    //selectFood(n,itemCost,0);
}

public static void possibilities(int length,String sofar,double[]itemCost,double money){

    if(length==0){
        //selectFood(sofar,itemCost,money,0);
        float totCost=0;

        double target=money/1.15;
        double minTip=money-target;

        char[]sofarList=sofar.toCharArray();
        for(int i=0;i<sofarList.length;i++){
            if(sofarList[i]=='1'){
                totCost+=itemCost[i];
            }

        }
        if(totCost<target){
        System.out.println(totCost);
        }

    }
    else{
        possibilities(length-1,sofar+"0",itemCost,money);
        possibilities(length-1,sofar+"1",itemCost,money);
    }
}

现在我回来了

0.0

8.49 6.35 6.99 5.35 7.49 5.35 6.49

Answer 1

您的方法可能存在的问题（除了它相对难以理解之外）是，您的方法实际上没有计算值（嗯……至少没有返回任何值），但它正在将某些内容打印到System.out。通常，您的方法应该计算某个或改变状态（例如，执行I/O），但不能同时执行这两种操作

一个简单的修复方法是将totCost存储在实例变量中，而不是打印它。也就是说，您可以更改您的行：

if(totCost < target){
    System.out.println(totCost);
}

到

if(totCost < target && highestPrice < totCost){
    highestPrice = totCost;
}

其中highestPrice是一个实例变量。现在您可以从selectFood方法访问highestPrice

请注意，这是一个黑客比一个干净的解决方案！如果possibilities方法将其计算的值作为常规返回值返回，那么代码将更干净

重新思考如何递归计算成本：

• 您将获得一组（在您的案例中是一个数组）价格和一个预算

• 对于每种价格，您可以选择购买商品并支付价格，也可以选择不购买商品并保留金钱

• 如果列表中只有一个项目，那么如果您负担不起该项目，您可以进行的最昂贵的组合是0，如果您负担不起该项目，或者该项目的价值

最后一点是基本情况（不考虑也可能有一个空数组）。所以你有一个基本情况

double possibilities(double[] items, double money){
  if (items.length == 1 && items[0] < money / 1.15) return items[0]; else return 0; 

这里需要注意的一点是：不要在代码中添加幻数（例如1.15）。它们没有任何意义

现在来看一般情况items.length>1：我们可以接受第一项，也可以不接受第一项。如果我们真的接受了，那么我们在剩下的项目上的花费就会减少。而且，我们只有在我们负担得起的情况下，也就是说，如果money>items[0]，我们才能接受它。对于剩余的钱和剩余的项目，我们递归调用该方法并获取更大的值

if(items.length > 1)
  if (items[0] < money / 1.15) 
    double totCostWithItem0 = items[0] + possibilities(/* items[1 to length], money - items[0] */)
    double totCostWithoutItem0 = possibilities(/* items[1 to length], money */)
    return totCostWithItem0 > totCostWithoutItem0 ? totCostWithItem0 : totCostWithoutItem0; 
  else // cannot afford it
    return possibilities(/* items[1 to length], money */

抱歉，这里的代码太草率了。因为您使用的是数组，所以需要将项1复制到新数组中的长度，以便在递归调用中传递它。而且我不太确定除以1.15应该做什么，所以你可能需要调整你递归传递的钱

Answer 2

要找到低于目标值的最大值，您需要一个变量来保持通过递归进行的每次迭代中的当前最大值

我更改了程序的逻辑以跟踪当前的最大值

public static void possibilities(int length,String sofar,double[]itemCost,double money){
    if(length==0){
        //selectFood(sofar,itemCost,money,0);
        float totCost=0;

        double target=money/1.15;
        double minTip=money-target;

        char[]sofarList=sofar.toCharArray();
        for(int i=0;i<sofarList.length;i++){
            if(sofarList[i]=='1'){
                totCost+=itemCost[i];
            }

        }
        if(totCost<target && totCost>max){
            max = totCost;
            System.out.println(totCost);
            for(int i=0;i<sofarList.length;i++){
                System.out.print(sofarList[i]);
            }   
            System.out.println("\n");
        }

    }
    else{
        possibilities(length-1,sofar+"0",itemCost,money);
        possibilities(length-1,sofar+"1",itemCost,money);
    }
}

您需要在类中将变量max声明为static

static double max=0;

我添加了print语句来显示在每个可行迭代中选择的最大值

所有迭代结束后，最大值存储在max变量中，为了跟踪菜单列表，我们需要再添加一个静态变量，如下所示

static String menulist=null;

我们需要在方法中赋值

if(totCost<target && totCost>max){
            max = totCost;
            menulist = sofarList;
}