Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[BoundedKnapsack] Finish the kata #638

Open
1 of 2 tasks
tcNickolas opened this issue Jul 15, 2021 · 2 comments
Open
1 of 2 tasks

[BoundedKnapsack] Finish the kata #638

tcNickolas opened this issue Jul 15, 2021 · 2 comments

Comments

@tcNickolas
Copy link
Member

tcNickolas commented Jul 15, 2021

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"
@vivanwin
Copy link
Contributor

I can pickup the first part to create a Jupyter frontend for the kata.

@tcNickolas
Copy link
Member Author

@vivanwin That will be great, thank you!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants