search

codezonediitj / pydatastructs

A python package for data structures and algorithms
https://pydatastructs.readthedocs.io/en/stable/
Other
200 stars 267 forks source link

Subset Sum (01 Knapsack) #303

Open RgnDunes opened 3 years ago

RgnDunes commented 3 years ago

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 commented 3 years ago

can you assign this to me? @RgnDunes

RgnDunes commented 3 years ago

@subhangi2731 go on. I assign it to you.

czgdp1807 commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

Can we solve 0-1 Knapsack formulation using CVXOPT?