Skip to content

#4367 Enhance Knapsack problem #4368

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
Merged
merged 19 commits into from
Sep 19, 2023
Merged

#4367 Enhance Knapsack problem #4368

merged 19 commits into from
Sep 19, 2023

Conversation

Manan-09
Copy link
Contributor

  • I have read CONTRIBUTING.md.
  • This pull request is all my own work -- I have not plagiarized it.
  • All filenames are in PascalCase.
  • All functions and variable names follow Java naming conventions.
  • All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.

Reduced space complexity of solution from O(n*w) to O(w)
Named variables better
Added testfile

All code is covered in testcases
Screenshot 2023-09-11 at 2 03 35 PM

@Manan-09 Manan-09 mentioned this pull request Sep 11, 2023
Closed
vil02
vil02 requested changes Sep 11, 2023
View reviewed changes
Copy link
Member

@vil02 vil02 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

There are two other solutions of that problem: DyanamicProgrammingKnapsack and KnapsackMemoization.java - what is the relation between them and the one you update?

Besides that I suggest some cosmetic changes.

@Manan-09
Copy link
Contributor Author

Seems like this is DyanamicProgrammingKnapsack duplicate of what I just refactored, and KnapsackMemoization.java is recursive solition of this problem.
But my solution has better space complexity with same TC

@Manan-09 Manan-09 requested a review from vil02 September 11, 2023 09:56
debasishbsws
debasishbsws previously approved these changes Sep 11, 2023
View reviewed changes
Copy link
Member

@debasishbsws debasishbsws left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good👍

@debasishbsws debasishbsws enabled auto-merge (squash) September 11, 2023 13:08
@debasishbsws debasishbsws enabled auto-merge (squash) September 11, 2023 13:08
@vil02
Copy link
Member

vil02 commented Sep 11, 2023

Seems like this is DyanamicProgrammingKnapsack duplicate of what I just refactored, and KnapsackMemoization.java is recursive solition of this problem. But my solution has better space complexity with same TC

@siriak how should we proceed?

@vil02 vil02 disabled auto-merge September 11, 2023 18:26
@siriak
Copy link
Member

siriak commented Sep 11, 2023

Please remove the duplicate, but leave the version with memoization as it's a different approach

siriak
siriak previously approved these changes Sep 12, 2023
View reviewed changes
vil02
vil02 requested changes Sep 12, 2023
View reviewed changes
Copy link
Member

@vil02 vil02 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I would suggest to use meaningful test names instead of comments. Names will appear in the output in case if they fail, Comments will not.

Thanks for adding missing tests!

Besides that: the code looks good.

@vil02 vil02 enabled auto-merge (squash) September 13, 2023 05:11
vil02
vil02 requested changes Sep 13, 2023
View reviewed changes
auto-merge was automatically disabled September 13, 2023 16:44

Head branch was pushed to by a user without write access

vil02
vil02 requested changes Sep 13, 2023
View reviewed changes
Copy link
Member

@vil02 vil02 left a comment •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

What if one of the entries of weights is negative or 0?

The following code:

Knapsack.knapSack(1, new int[]{0, 0, 0, 0}, new int[]{1, 1, 1, 1})

gives me 16 and I think the correct answer should be 4.

@Manan-09
Copy link
Contributor Author

What if one of the entries of weights is negative or 0?

The following code:

Knapsack.knapSack(1, new int[]{0, 0, 0, 0}, new int[]{1, 1, 1, 1})

gives me 16 and I think the correct answer should be 4.

Knapsack problem have positive weights normally, should we add extra check for non positive weights ?

@vil02
Copy link
Member

vil02 commented Sep 14, 2023 •
edited
Loading

Knapsack problem have positive weights normally, should we add extra check for non positive weights ?

Yes! Throwing an error is the best way of saying that non-positive weights are forbidden.

vil02
vil02 requested changes Sep 17, 2023
View reviewed changes
vil02
vil02 requested changes Sep 17, 2023
View reviewed changes
vil02
vil02 requested changes Sep 17, 2023
View reviewed changes
vil02
vil02 reviewed Sep 19, 2023
View reviewed changes
@vil02 vil02 enabled auto-merge (squash) September 19, 2023 19:51
@vil02 vil02 merged commit 12b6c29 into TheAlgorithms:master Sep 19, 2023
@vil02 vil02 mentioned this pull request Sep 22, 2023
Merged
5 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@vil02 vil02 vil02 approved these changes

@siriak siriak siriak left review comments

@BamaCharanChhandogi BamaCharanChhandogi BamaCharanChhandogi left review comments

@yanglbme yanglbme Awaiting requested review from yanglbme yanglbme is a code owner

@debasishbsws debasishbsws Awaiting requested review from debasishbsws

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
5 participants
@Manan-09 @vil02 @siriak @debasishbsws @BamaCharanChhandogi