Consider this way of solving the Subset sum problem: def subset_summing_to_zero (activities): subsets = {0: []} for (activity, cost) in activities.iteritems(): old_subsets = subsets subsets = ...

I have A menu dict item as key and price as value. There may exist a combination of item that will be bit cheaper than single item. For exa: menu = { ('burger',) : 5.00, ('pizza',) : 12.00, ('c...

This was a question on our Algorithms final exam. It's verbatim because the prof let us take a copy of the exam home. (20 points) Let I = {r1,r2,...,rn} be a set of n arbitrary positive intege...

This is a follow-up to my previous question. I still find it very interesting problem and as there is one algorithm which deserves more attention I'm posting it here. From Wikipedia: For the case ...

I have a function 'subsets' which generate all the subsets of a given set: subsets :: [Int] -> [[Int]] subsets [] = [[]] subsets (x:xs) = subsets xs ++ map (x:) (subsets xs) How can I combine...

Given: array of integers value K,M Question: Find the maximum sum which we can obtain from all K element subsets of given array such that sum is less than value M? is there a non dynamic programm...

The subset sum problem is well-known for being NP-complete, but there are various tricks to solve versions of the problem somewhat quickly. The usual dynamic programming algorithm requires space t...

I have a problem related to the subset sum problem and am wondering if the differences make it easier, i.e. solvable in a reasonable amount of time. Given a value V, a set size L, and a sequence o...

Given two lists of numbers and a list of totals (none in any particular order): a = [1,2,3] b = [4,5,6] c = [6,7,8] How can I find all sets of pairs d where d[k] = (a[i], b[j]) such that c[k] = ...

(Before you reply with a link to another SO question or close this as a duplicate please read the question carefully. This is different than the standard variant of this problem and I've searched f...

given a unsorted set of n integers, return all subsets of size k (i.e. each set has k unique elements) that sum to 0. So I gave the interviewer the following solution ( which I studied on GeekView...

How would you use dynamic programming to find the list of positive integers in an array whose sum is closest to but not equal to some positive integer K? I'm a little stuck thinking about this.

I have several arrays of numbers (each element of the array can only take a value of 0 or 1) like this v1: 1; 0; 0; 1; 1; v2: 0; 1; 0; 0; 1; v3: 1; 1; 0; 1; 0; v4: 1; 0; 0; 1; 0; v5: 1; 1; 0...

Following from these question Subset sum problem and Sum-subset with a fixed subset size I was wondering what the general algorithm for solving a subset sum problem, where we are forced to use EXAC...

I've been breaking a sweat over this question I've been asked to answer (it's technically homework). I've considered a hashtable but I'm kind of stuck on the exact specifics of how I'd make this wo...

following Problem: I have a MySQL database with songs in it. The database has the following structure: id INT(11)(PRIMARY) title VARCHAR(255) album VARCHAR(255) track INT(11) duration INT(11) T...

I have a real-world problem (not homework!) that requires finding the sum of a subset of set A that equals the sum of a subset of some other set B. A very similar question with a helpful answer is...

I know this can be done by sorting the array and taking the larger numbers until the required condition is met. That would take at least nlog(n) sorting time. Is there any improvement over nlog(n)...

I came up with a new algorithm to solve the subset sum problem, and I think it's in polynomial time. Tell me I'm either wrong or a total genius. Quick starter facts: Subset sum problem is an NP-c...

I was reading about the subset-sums problem when I came up with what appears to be a general-purpose algorithm for solving it: (defun subset-contains-sum (set sum) (let ((subsets) (new-subset) (n...

The problem is the following: You are given a set of positive integers { a1 , a2 , a3 , ... , an } in which there are no same numbers ( a1 exists only once ,a2 exists only once,...) eg A = {12 , 5...

I'm looking for an algorithm which can take two sets of integers (both positive and negative) and find subsets within each that have the same sum. The problem is similar to the subset sum problem ...