Subset Sum (01 Knapsack)

[RgnDunes]

Description of the problem

Adding a function for Subset Sum (01 Knapsack) that would be helpful in solving multiple questions like Subset Sum Problem, Equal Sum Partition Problem, Count of Subsets Sum with given Sum, Minimum Subset Sum Difference, Count of number of Subset with a given difference, Target Sum and many more . Writing this function will help us save a lot of code while coding.

Example of the problem

Problem isn't a bug.

References/Other comments

https://leetcode.com/problems/partition-equal-subset-sum/ https://leetcode.com/problems/target-sum/

Refer these two questions from leetcode which uses Subset Sum concept.

[subhangi2731]

can you assign this to me? @RgnDunes

[RgnDunes]

@subhangi2731 go on. I assign it to you.

[czgdp1807]

Please read https://github.com/codezonediitj/pydatastructs/wiki/Issue-Policy This seems like a good idea. However, before jumping on to code, we should discuss what APIs(how the function call will like look) can support using solution of 0-1 Knapsack problem to solve other problems like mentioned in the OP.

[Smit-create]

The main problem I see here is the constraints on the range of sum. There are many techniques present using DP, bitsets for subset sum tasks, but the range in that is such that it fits time and memory constraints.

[czgdp1807]

Well, can the solution to 0-1 Knapsack problem be generalized to other problems? A function for 0-1 knapsack would be very specific. However, the way it is formulated here can motivate the creation of an optimisation module to solve various kinds of formulation with pseudo-polynomial and non-polynomial algorithms.

[Smit-create]

However, the way it is formulated here can motivate the creation of an optimisation module

There exists a module of solving optimisation problems. Have a look https://cvxopt.org/

[czgdp1807]

Can we solve 0-1 Knapsack formulation using CVXOPT?