Skip to content
This repository was archived by the owner on Aug 21, 2024. It is now read-only.
This repository was archived by the owner on Aug 21, 2024. It is now read-only.

[BoundedKnapsack] Finish the kata #638

@tcNickolas

Description

@tcNickolas

A follow-up for #416. The remaining work items:

  • Develop Jupyter Notebook "frontend" for the kata, include it in the list of all katas and the CI build
  • Develop part III "Solving knapsack problems using Grover's search". This will be based on the part III from Create new kata: Bounded Knapsack #457, with the following changes:
    • We should have tasks to solve both 01 and multi-item variants of the problem (4 tasks in total)
    • We should use an approach similar to SolveSATWithGrover, which just tries search with different numbers of iterations, rather than use classical bruteforce check to define the number of solutions.
    • Look into adding more test cases to the tasks in part III without slowing them down unreasonably. Currently using it to solve one instance of a problem takes 45 seconds on my machine, so 2 tests will definitely take too long. Might want to reduce the size of the problem instance.
    • We could probably speed up the solution by dropping the constraint check for number of selected items being less than or equal to the number of available copies and building this check into Grover's search. This might be part IV - "Optimizing Grover's search"

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions