主页 / 问题 / 1532779
Accepted
Настя
Asked:2023-07-27 21:28:00 +0000 UTC2023-07-27 21:28:00 +0000 UTC

背包问题的变体，while循环没有结束（python）

  • 772

解决了问题：

Пират нашел на захваченном корабле N золотых слитков, каждый из 
которых имеет значительный вес ( W i для слитка с номером i ). 
Во время боя захваченный корабль получил серьёзные повреждения 
и вот-вот затонет. Пират может увезти на шлюпке на свой корабль 
только C килограммов груза. Какие слитки он должен выбрать, 
чтобы увезти как можно больше золота?

Входные данные
Первая строка содержит грузоподъёмность шлюпки пирата C в 
килограммах ( 1 ≤ C ≤ 5000 ). Во второй строке записано количество 
найденных золотых слитков N ( 1 ≤ N ≤ 100 ). В третьей строке 
записано N натуральных чисел: массы каждого слитка, разделённые 
пробелами, в порядке возрастания (неубывания).

Выходные данные
В первой строке программа должна вывести наибольшую массу золотых 
слитков, которые может вывезти пират. Во второй строке нужно 
вывести массы взятых слитков в порядке убывания (невозрастания). 
Если у задачи есть несколько вариантов решения, достаточно вывести 
любой из них.

Примеры
входные данные
800
4
200 400 500 700
выходные данные
700
500 200

这似乎是背包问题的一种变体，代码如下：

n=int(input()) 
m=int(input()) 
a=list(map(int, input().split()))  
ans=[]
while sum(ans)<n:
    u=0 
    for i in a:
        if sum(ans)+i<=n and i>u and i not in ans:
            u=i 
    ans.append(u) 
print(sum(ans))
print(ans)

但是当我输入输入数据时，数字的输入并没有结束，另外，我认为如果列表a中某个元素重复，程序会给出错误的答案，我不知道该怎么办......请帮我修改一下代码！！！！

python

3 个回答

  1. Best Answer

    使用动态规划的解决方案。
    我们以总重量的长度开始一个表格，其中i第-个单元格包含物品的重量w，使用它可以获得重量i。
    如果存在不使用权重为 的指定对象的组合，则可以收集这样的权重i-w。如果金额i已收集，请勿更改主题（不影响最大结果的值，仅影响列表的排序）

    因此，我们依次对物体（锭）进行排序。我们从最后开始讨论，以排除在一个组合中多次使用锭的情况。

    填充后，我们找到最大可能的数量，并迭代数组以找出由哪些条组成。原始列表的指定顺序和遍历顺序给出非升序排序结果

    def pirate(C, weights):
    a =[0]*(C+1)
    a[0] = -1

    for w in weights:
        for i in range(C, w-1,-1):
             if a[i-w] and a[i] == 0:
                a[i] = w

    #print(a)  #можно вывести для контроля

    idx = C
    while a[idx]==0:
        idx -= 1

    maxx = idx
    res = []
    while idx:
        res.append(a[idx])
        idx -= a[idx]
    return maxx, res

print(pirate(800, [100, 320, 320, 610]))

>>>740, [320, 320, 100]
    • 2

  2. 问题

    让我们输入数据：

    100
1
1

    程序将循环。数组ans将具有形式[1, 0, 0, ..., 0]并无限增长。我无法纠正您的解决方案，因为我不明白您想如何解决问题。

    可能的解决方案

    我们将积累一个字典：键 - 数量，值 - 锭的重量。对于每个新锭，我们都会遍历所有金额并将新金额添加到字典中。新的金额是旧的金额加上元宝。超过船只承载能力的数量将被跳过。

    处理完所有的锭后，我们从字典中选择最大数量，并从它下降到零。时间复杂度不超过CN，内存复杂度不超过C。

    c = int(input()) 
input()  # skip n

sums = {0: 0}
for w in map(int, input().split()):
    sums.update((w + s, w) for s in tuple(sums.keys()) if w + s <= c)

s = max(sums.keys())
print(s)
while s > 0:
    w = sums[s]
    print(w, end=' ')
    s -= w
print()
    • 1 
  3. def pirate_gold(C, N, weights):
    dp = [[0 for _ in range(C + 1)] for _ in range(N + 1)]

    for i in range(1, N + 1):
        for w in range(1, C + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + weights[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]

    selected_weights = []
    i, w = N, C
    while i > 0 and w > 0:
        if dp[i][w] != dp[i - 1][w]:
            selected_weights.append(weights[i - 1])
            w -= weights[i - 1]
        i -= 1

    selected_weights.sort(reverse=True)
    return dp[N][C], selected_weights


# Пример использования
if __name__ == "__main__":
    C = 800
    N = 4
    weights = [200, 400, 500, 700]

    max_gold, selected_weights = pirate_gold(C, N, weights)
    print(max_gold)
    print(*selected_weights)
    • 0

相关问题