Skip to content

Enhancement of the knapsack algorithm #9266

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.

Sign up for GitHub

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

Jump to bottom
Closed
Jiang15 opened this issue Oct 1, 2023 · 4 comments · May be fixed by #9295 or #10180
Closed

Enhancement of the knapsack algorithm #9266

Jiang15 opened this issue Oct 1, 2023 · 4 comments · May be fixed by #9295 or #10180
Labels
enhancement This PR modified some existing files

Comments

@Jiang15
Copy link
Contributor

Jiang15 commented Oct 1, 2023

Feature description

There is a recursive implementation of 0-1 knapsack problem. The idea is to enhance it with code optimization and feature extension.

  • Optimize the recursion with memorization (DP) which reduces the complexity to O(KN).
  • Implement knapsack algorithm which gives the option to allow the items been repetitively picked multiple times, i.e, either 0-1 or 0-N knapsack problem.
@Jiang15 Jiang15 added the enhancement This PR modified some existing files label Oct 1, 2023
@balkishan69

This comment was marked as off-topic.

Sign in to view
@abhishek09827

This comment was marked as off-topic.

Sign in to view
@Jiang15 Jiang15 mentioned this issue Oct 1, 2023
Open
14 tasks
@Jiang15
Copy link
Contributor Author

Jiang15 commented Oct 1, 2023

I already created a PR here #9295

@dasdebanna dasdebanna mentioned this issue Oct 4, 2023
Closed
14 tasks
swapnil290502 added a commit to swapnil290502/Python that referenced this issue Oct 4, 2023
@swapnil290502
Create Enhancement of the knapsack algorithm TheAlgorithms#9266
767d4f2
swapnil290502 added a commit to swapnil290502/Python that referenced this issue Oct 4, 2023
@swapnil290502
Create Enhancement of the knapsack algorithm TheAlgorithms#9266
bec27f5
swapnil290502 added a commit to swapnil290502/Python that referenced this issue Oct 4, 2023
@swapnil290502
Merge pull request #2 from swapnil290502/swapnil290502-patch-2-1
170f935 
Create Enhancement of the knapsack algorithm TheAlgorithms#9266
swapnil290502 added a commit to swapnil290502/Python that referenced this issue Oct 4, 2023
@swapnil290502
Revert "Create Enhancement of the knapsack algorithm TheAlgorithms#9266"
7842bc0
swapnil290502 added a commit to swapnil290502/Python that referenced this issue Oct 4, 2023
@swapnil290502
Merge pull request #3 from swapnil290502/revert-2-swapnil290502-patch…
821dae5 
…-2-1

Revert "Create Enhancement of the knapsack algorithm TheAlgorithms#9266"
This was referenced Oct 5, 2023
Closed
Open
@cclauss
Copy link
Member

cclauss commented Oct 15, 2023

CONTRIBUTING.md says:

Do not create an issue to contribute an algorithm. Please submit a pull request instead.

@cclauss cclauss closed this as completed Oct 15, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement This PR modified some existing files
Projects
None yet
Milestone
No milestone
4 participants
@cclauss @Jiang15 @abhishek09827 @balkishan69