Вариация задачи о рюкзаке, цикл while не заканчивается (python)

Question

Вариация задачи о рюкзаке, цикл while не заканчивается (python)

Рейтинг: 0Ответов: 3Опубликовано: 27.07.2023

Решала задачу:

Пират нашел на захваченном корабле 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 алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 2Принят

Решение с помощью динамического программирования.
Заводим таблицу длиной в общий вес, в которой i-я ячейка содержит вес предмета w, с использованием которого может быть получен вес i.
А собрать такой вес можно, еcли существует комбинация без использования указанного предмета весом 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]

Answer 2

▲ 1

Проблема

Введём данные:

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()):
    for s in tuple(sums.keys()):
        if w + s <= c:
            sums.setdefault(w + s, w)

s = max(sums.keys())
print(s)
while s > 0:
    w = sums[s]
    print(w, end=' ')
    s -= w
print()

Answer 3

▲ 0

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)

Вариация задачи о рюкзаке, цикл while не заканчивается (python)

Ответы

Проблема

Возможное решение