[FEATURE] Reduce space complexity of 0-1 Knapsack problem

[Manan-09]

Detailed description

We can implement 0-1 knapsack problem in O(C) space complexity , where C is weight capacity of items we are allowed to take.

As in DP table we are only interacting with above row , we just have to store one row of information , so we can reduce space complexity here.

Here is reference in which I optimised Java implementation for this problem

Context

Current implementation takes O(N * C) space complexity, which is not the optimal, we can gain same result with same Time complexity and reduced space compexity.

Possible implementation

No response

Additional information

No response

[AniketShirou]

Please Assign This Issue To Me

[Manan-09]

@AniketShirou , actully I cannot assign this to you but you work on it, No problem.

[harjasae2001]

I have done this problem and variations of this problem too and I am quite familiar with the concept of using two separate vectors and updating them one by one. Kindly please assign this issue to me.

[github-actions[bot]]

This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[2021110906]

?

[github-actions[bot]]

This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[github-actions[bot]]

Please ping one of the maintainers once you add more information and updates here. If this is not the case and you need some help, feel free to ask for help in our Gitter channel or our Discord server. Thank you for your contributions!