[48in24 Exercise] [08-13] Knapsack

This issue is a discussion for contributors to collaborate in getting ready to be featured in 48in24. Please refer to this forum topic for more info.


We will be featuring Knapsack from Aug 13 onwards.

Staff jobs

These are things for Erik/Jeremy to do:

  • ☐ Check/update exercise in Problem Specifications
  • ☐ Create + schedule video

Community jobs

For each track:

  • Implement Knapsack
  • Add approaches (and an approaches introduction!) for each idiomatic or interesting/educational approach.
  • Add video walkthroughs (record yourself solving and digging deeper into the exercise).
  • Highlight up to 16 different featured exercises (coming soon)

Existing Approaches

You can use these as the basis for approaches on your own tracks. Feel free to copy/paste/reuse/rewrite/etc as you see fit! Maybe ask ChatGPT to translate to your programming language.

  • dynamic-programming (java)
  • recursive (java)

Track Statuses

You can see an overview of which tracks have implemented the exercise at the #48in24 implementation status page.

I’ve currently gathered the following solutions to feature:

  1. Gleam: recursion
    Use recursion (not tail recursive)

  2. Python: generate all combinations and then find the best result
    Generate all combinations to then find best result, not optimal

  3. C++: dynamic programming
    Use dynamic to only calculate values once, by building up all max values

  4. Prolog: constraints-based
    Define the problem as a series of constraints and let the solver find the answer

If anyone has more suggestions, do let us know!

I haven’t done this one before so I’ll add the exercise to CoffeeScript and Vim script.

This is another dynamic programming approach (using Python’s cached decorator) combined with recursion: IsaacG's solution for Knapsack in Python on Exercism

I’m not sure how different it is from the C++ one.

1 Like

For LFE:

1 Like