I am not fully sure, but does the code wrongly assume what is numbers are even and odd?

@xcthulhu, please take a look at my new solution. It passes 1862 tests but it still times out.

Thank you.

Of course, but only after passing them. The idea is to prevent solving the task in a way that only the test cases pass (without solving it generally).

Any tips on how to solve this without combinatory? I'm stuck here.

Hey! This got a bit lost in my feed.

Sadly, this isn't a very efficient solution, since all of those set inserts take O(log(n)). So I suspect this algorithm scales at least O(n log(n)).

Moreover, triplets = product(range(n), repeat=3) scales like O(n³)...

It should be:

Test.assert_equals(knapsack(100, [[1, 1], [3, 4]]), [100])

I assume you mean [100, 0] for the quantities (the last brackets)

Am I misunderstanding the greedy solution?

Unless you are reading the items as [value, size] (they are [size, value]), you are misunderstanding the greedy solution. The greedy solution will always add the item with the highest value-to-size ratio that can fit in the knapsack.

The two ratios here are 1.0 for the [1, 1] item and 1.3 for the [3, 4] item. Therefore, the [3, 4] item will be prioritized. 33 of this item can fit in the 100-size knapsack, taking up 99 of the knapsack. That leaves 1 space for a [1, 1] item to fill.

I think this test is wrong:

Test.assert_equals(knapsack(100, [[1, 1],
[3, 4]]), [1, 33])

It should be:

Test.assert_equals(knapsack(100, [[1, 1],
[3, 4]]), [100])

Am I misunderstanding the greedy solution?

If you go into "Account Settings" and turn on "CODEWARS LABS" you can post a kumite there...

@xcthulhu, I can't post a kumite because I haven't earned the right to see the solutions of the kata (because I cannot solve it).

I had the same problem. If I move numbers generation inside a function it times out(system tests only), but outside a function works in 55ms.

Also, as I've said elsewhere, there are other optimizations to consider aside from just getting your time complexity down.

That being said, you can get away with slower solutions in javascript because it has a proper JIT...