Задача: Рюкзак

Question

Рюкзак
Найдите максимальный вес золота, который можно унести в рюкзаке вместительностью s, если есть n золотых слитков с заданными весами.
Входные данные
Первая строка содержит одно число s (1 ≤ s ≤ 10000). Далее следует n (1 ≤ n ≤ 300) неотрицательных чисел, не превосходящих 100000 - веса слитков.
Выходные данные
Выведите искомый максимальный вес.
=======================================
Входные данные #1
10
1 4 8
Выходные данные #1
9
=======================================
Входные данные #2
20
5 7 12 18
Выходные данные #2
19
Я ее сделал перебором, но мой код очень долго работает ...
Вот мой код:
https://code.sololearn.com/ctRX0XkcIRff/?ref=app

Answer 1

Alexander your code seems good, but it would take a lot of time to execute. Also, what is it you neede help with, does your code not work properly ?

Answer 2

Alexander whoops 😂😂 let me check. Do you have any other test cases ?
EDIT: lmao my code is completly wrong. I thought you were only supposed to have two numbers together, not many at the same time. Sorry! I'll try in a bit.

Answer 3

You can get more help if you ask in english, you seem to know it as well. I said so because I noticed you posted it yesterday but didn't get any answer (I think).

Answer 4

Alexander Okay, I'll try.
EDIT:
Here is my code, I think it will be faster than the permutations:
https://code.sololearn.com/cjWpEgsH1LRN/?ref=app
(let me know if my code is slow or doesn't work)

Answer 5

Aymane Boukrouh Thanks for the advice. I understand. I'm just afraid if I translate the task into English by a Google translator, then the person may not understand the task correctly. 😶

Answer 6

Aymane Boukrouh
Knapsack
Find the maximum weight of gold that can be carried out in a knapsack of capacity s, if there are n gold ingots with specified weights.
Input
The first line contains one number s (1 ≤ s ≤ 10000). Then given n (1 ≤ n ≤ 300) non-negative integers, not exceeding 100000 - the weights of ingots.
Output
Print the desired maximum weight.
===================================
Input example #1
10
1 4 8
Output example #1
9
===================================
Input example #2
20
5 7 12 18
Output example #2
19
===================================

Answer 7

Aymane Boukrouh
I need help writing faster code that will solve the "Knapsack" problem and learn about different methods for solving tasks.

Answer 8

Alexandr Your past code worked 50% from 100% and the new 93% from 100%.
7% is the time limit

Answer 9

Hi! From where you got this task? I need it also 😉

Answer 10

I checked this site! Its very good! Thanks! 😉😁👍

Answer 11

I will coming back soon...

Answer 12

in fact, everyone scolds Python for its slowness, but you made an attempt to squeeze the maximum possible out of it 😁 do you solve problems only for yourself or is this part of your mandatory coding in an educational institution?

Answer 13

I don't want to see the finished solution yet, as I will try to solve this problem on my own

Answer 14

Then... if you good in english you can try solve exercises on codewars.com
there you become a karate fighter and try to pass the levels of tasks sorted by difficulty. you can also arrange fights with other users there

Answer 15

Alexandr Your code works fine but with large numbers slow.

Answer 16

Ярослав Вернигора(Yaroslav Vernigora)
Hi;) Website: e-olymp, task #4831.

Answer 17

Aymane Boukrouh The code works faster but gives incorrect answers.

Answer 18

Aymane Boukrouh Huh it happens😁 .. sorry, but I have no more examples.

Answer 19

Ярослав Вернигора(Yaroslav Vernigora) 😊😉👌👍

Answer 20

Ярослав Вернигора(Yaroslav Vernigora)
This task has already been solved by Alexandr, here is its code that works great👌:
from itertools import combinations
n = int(input())
ar = [int(x) for x in input().split() if int(x) <= n]
def maxsearch(m):
if sum(m) <= n:
return sum(m)
maxx = 0
for i in range(1, len(m) + 1):
res = filter(lambda x: maxx < x <= n, map(sum, combinations(m, i)))
for y in res:
if y > maxx:
maxx = y
if maxx == n:
return maxx
return maxx
print(maxsearch(ar))