How to speed up code?

Question

Backpack with the masses
Set n objects of mass m1, m2, ..., mN and c1, c2, ..., cN respectively.

They fill a backpack with a weight not exceeding m. Identify a set of items that can be carried in a backpack, which has the highest value.

Incoming data
The first line contains an integer m that does not exceed 10000.

The second line contains n (n ≤ 100) positive integers m_i that do not exceed 100.

The third line contains n positive integers c_i that do not exceed 100.

Output data
Display the item numbers (numbers 1 through n) that will be included in the highest value backpack.

===================================
Input # 1
6
2 4 1 2
7 2 5 1
===================================
Output # 1
1
3
4
===================================

I have written code that can solve this problem, but something works very slowly and may even have errors. What you need to do to make the program run faster.

My code:

https://code.sololearn.com/cKS3aB8Lcv96/?ref=app

Answer 1

Ah, yes. The 0-1 Knapsack problem.

Your solution is indeed not very efficient. You can improve using Dynamic Programming.

Take a look at this article:
https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

Answer 2

Diego Thank you 👍

Answer 3

Diego With your tooltip, I have solved this problem😁😊👍👌

Thank you very much!😉

https://code.sololearn.com/cIvblY0gw6G9/?ref=app

Answer 4

Рюкзак с массами
Дано n предметов массой m1, m2, ..., mn и стоимостью c1, c2, ..., cn соответственно.

Ими наполняют рюкзак, который выдерживает вес не более m. Определите набор предметов, который можно унести в рюкзаке, имеющий наибольшую стоимость.

Входные данные
В первой строке задано натуральное число m, не превышающее 10000.

Во второй строке заданы n (n ≤ 100) натуральных чисел mi, не превышающих 100.

В третьей строке заданы n натуральных чисел ci, не превышающие 100.

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

===================================
Входные данные #1
6
2 4 1 2
7 2 5 1
===================================
Выходные данные #1
1
3
4
===================================