ボニーとクライドは、宝石の物語を盗もうと決心した 2 人の泥棒です。それぞれが戦利品を運ぶために使用するバッグを持っていますが、各バッグは壊れる前に n グラムの宝石しか保持できません。彼らが強盗している店には、それぞれ独自の重量と金銭的価値を持ついくつかの異なる種類の宝石があります。
- バッグを埋めるためのクライドのアプローチは「貪欲」です。これは、一度に 1 つずつバッグに宝石を追加することを意味し、次にどの宝石をバッグに入れるかを選択するとき、彼は常に、重量制限を超えない最も価値の高い宝石を選択します。
- Clyde は、価値が同じで重さが異なる 2 つの宝石のどちらかを選択できる場合、常に軽い方を選択します。
- ボニーは、バッグの詰め方が賢ければ、クライドよりも価値のある荷物を持って宝石店を出ることがよくあると考えています。あなたの仕事は、これが真実であることを示す手助けをすることです。そのためには、jewelthief.py というプログラムを作成します。このプログラムは、入力として宝石のリスト (それぞれの重量はグラム単位で値はドル単位) とバッグの重量制限を受け取ります。貪欲なアプローチを使用して選択された場合、プログラムはバッグ内の宝石の合計値を出力し、その値が可能な最大値とどのように比較されるかを動的計画法を使用して計算します。入力は標準入力を介して与えられます。
- 入力の最初の行は、バッグが保持できる最大重量に対応する単一の整数で構成されます。
- 次の各行は 2 つの整数で構成され、新しい宝石タイプを定義します。
- 最初の整数はグラム単位の宝石の重量で、2 番目の整数はその宝石のドル単位の値になります。
強盗されている店には、各タイプの宝石が無制限にあると想定できることに注意してください。
サンプル入力 1:
10 3 4 2 3 1 1サンプル出力 1:
The greedy approach would steal $13 of jewels The optimal approach would steal $15 of jewelsサンプル入力 2:
575 125 3000 50 100 500 6000 25 30サンプル出力 2:
The greedy approach would steal $6130 of jewels The optimal approach would steal $12130 of jewelsサンプル入力 3:
1500 151 150 150 150サンプル出力 3:
The greedy approach would steal $1500 of jewels The optimal approach would steal $1500 of jewels
私はPythonにまったく慣れていないので、この質問は私にとって非常に混乱しています。宝石の価値を計算し、合計して両方の泥棒の最大重量で停止する方法を理解するのに苦労しています.
これまでの私のコードは次のとおりです。
bag=input('max_weight of bag: ') #weight of the bag
Clyde_value=0 #initialize weight and value for both thieves
Clyde_weight=0
Bonnie_value=0
Bonnie_weight=0
while True:
try:
line=input() #input weights and values at once
except:
break
if len(line)==0:
break
a=list(map(int,line.split(None)))
if len(line)<1:
break
lst=[]
lst.append(a)
#print(a) #this will printout the list below when enter the sample input 1
#[3, 4]
#[2, 3]
#[1, 1]
weight_jewel=a[0] #print this will give 3 2 1 for sample input 1
value_jewel=a[1] #print this will give 4 3 1 for sample input 1
while Clyde_weight <= bag: #start calculating clyde's jewel value
私のコードがこの質問でうまく機能するかどうかはよくわかりません。アドバイスやヒントを教えてください。そうしないと、例が素晴らしいでしょう。どうもありがとう。