1

邦妮和克莱德是两个决定抢劫珠宝故事的小偷。每个人都有一个用来携带战利品的袋子，但每个袋子在破裂之前只能容纳 n 克珠宝。他们抢劫的商店有几种不同类型的珠宝，每种都有自己的重量和货币价值。

  • 克莱德填满他的包的方法是“贪婪的”。这意味着他每次将珠宝添加到他的包中，并且在选择下一个放入包中的珠宝时，他总是选择不会超过重量限制的最高价值的珠宝。
  • 如果克莱德曾经在价值相等但重量不同的两颗珠宝之间做出选择，他总是会选择较轻的那颗。
  • Bonnie 认为，如果她在装包的方式上更聪明，她离开珠宝店的时候往往会比 Clyde 更有价值。你的任务是帮助证明这是真的。为此，您将编写一个程序jewelthief.py，该程序将输入一个珠宝列表（每个珠宝的重量以克为单位，价值以美元为单位）和袋子的重量限制。然后，您的程序将在使用贪婪方法选择时输出包中珠宝的总值，以及该值如何与您将使用动态编程计算的最大可能值进行比较。输入将通过标准输入给出。
  • 输入的第一行将由一个整数组成，该整数对应于袋子可以容纳的最大重量。
  • 接下来的每一行将包含两个整数，并将定义一个新的珠宝类型。
  • 第一个整数是以克为单位的珠宝重量，第二个整数是该珠宝的美元价值。

请注意，您可以假设被抢劫的商店拥有无限数量的每种珠宝。

样本输入 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

我不太确定我的代码是否能很好地解决这个问题。请给我一些建议和提示，否则一个例子会很棒。太感谢了。

4

0 回答 0