0

私の最後の投稿をすでに読んでいる人々のために、私はこれに対して別の解決策を持っています。ただ立ち去らないでください。

これは学校からの課題の質問です(長い話で申し訳ありませんが、私はすでにそれを短くしてみました)

私は自分にどれだけのお金があるかに基づいて食べ物を注文する傾向があります。私はサービスに関係なく少なくとも15%のチップを支払うのが好きで(すでに特定の週のパフォーマンスを十分に評価しています)、正しいものを見つけようとしてウェイトレスが変更を返すのを待って、お金を与えるプロセス全体が嫌いです適切なヒントを作成するために変更します。私がしていることは、私が持っているお金に最も合う食べ物の組み合わせのメニューを調べることです。私がベストマッチと言うとき、私は下に行かずに15%に最も近いことを意味し、私は各食品を1回だけ選びます。ご想像のとおり、これらすべてを計算するには少し時間がかかるので、使用できるメソッドを作成してください。

このメソッドは、次のメニューでのみ機能する必要があります。

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というメソッドを作成します。このメソッドは、私が持っている金額をパラメーターとして受け取り、選択範囲を画面に出力し、小数点以下1桁に丸めたままにするチップのパーセンテージを返します。二人で食べられる以上の食べ物があっても心配しないでください、私はしばしばより大きなグループで出かけます。

出力例:

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を超えるお金の入力には時間がかかりすぎます。ブールリストを追加して「取った」ことを示します。どれがすでに選ばれていますが、それはまったく機能せず、私を混乱させました:(

コメントアウトされているすべての部分は、食品の選択の出力用です。また、selectFoodメソッドは現在無効であり、値を返さないことはわかっていますが、修正する方が簡単だと思います。私が今気にしているのは、このパーセンテージ部分をどのように機能させるかです。

私の質問を読んでいただきありがとうございます。私を助けていただければ幸いです。または、私が求めているものが得られない場合は、コメントを残してください。

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よりも少ないままになるようにします。

再帰ツリーの各ブランチは、購入できる製品の1つの組み合わせを表します。これが私のソリューションとあなたのソリューションの主な違いです。ツリーの最初のブランチで、2つの可能性を評価します。「BanderaPizza Bread」を購入するか、購入しないかのどちらかです。ブランチの第2レベルでは、「ボストンのピザパン」を購入する必要があるかどうかを評価します。再帰呼び出しのたびに、まだ使うお金が残っているかどうか(その時点でリストの次の項目を確認します)、またはこの注文が「使いすぎ」であるかどうかを知る必要があります。その時点で私はこれをあきらめます。組み合わせ(他のものを購入すると、さらに高価になるためです!)。

作成/破棄する必要のある配列の数を減らすために、このブランチで購入することを決定したアイテムを指定するビットフィールドとして「選択された」整数を使用しています。ビットが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);
}

これは非常に効率的に実行されるはずです。なぜなら、各食品は再帰のレベルを1つ追加するだけであり、再帰的なブランチの多くは早期に(購入が高すぎるとすぐに)切り落とされるからです。

最後に、結果を印刷する必要があります。

    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 に答える