Question

Помогите пожалуйста решить задачу. Желательно C++ питон, но можно и паскаль.

Путешествие

Один торговец собрался в дорогу. У него имеется N предметов (N≤20). Известны вес и стоимость каждого предмета. Помогите ему заполнить рюкзак предметами так, чтобы суммарная стоимость предметов в рюкзаке была максимальна. Рюкзак может выдержать не более 40 кг веса. Величины веса и стоимости – натуральные числа ≤100.


Формат ввода

В первой строке вводится количество предметов N. Со второй строки через пробел вводится вес и стоимость предмета соответственно.


Формат вывода

Выводятся номера предметов, которые взяли в рюкзак в любом порядке. Выводится вес и стоимость всех предметов в рюкзаке.



Ввод

3

10 14

19 12

12 15

Вывод

3

1

22 29

Answer 1

Ответ:

Вот код на питоне:

N = int(input())

objects = []

for i in range(N):

   objects.append(list(map(int, input().split())))

rezult = []

summ = 0

price = 0

while summ <= 40:

   Max = 0

   index = -1

   for i in objects:

       if i[1] > Max and i[0] + summ <= 40 and not objects.index(i) in rezult:

           Max = i[1]

           index = objects.index(i)

   if index == -1:

       break

   rezult.append(index)

   summ += objects[index][0]

   price += objects[index][1]

for i in rezult:

   print(i + 1)

print(summ, price)

Объяснение:

При необходимости могу пояснить построчно.