{"id":611,"date":"2008-12-07T13:17:07","date_gmt":"2008-12-07T12:17:07","guid":{"rendered":"http:\/\/www.navision-blog.de\/2008\/12\/07\/subsetsum-in-ons\/"},"modified":"2022-12-30T13:29:50","modified_gmt":"2022-12-30T13:29:50","slug":"subsetsum-in-ons","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2008\/12\/07\/subsetsum-in-ons\/","title":{"rendered":"SubsetSum in O(nS)"},"content":{"rendered":"

The “Subset Sum”-problem is given as the following:<\/p>\n

\n

SUBSET SUM
Input: Numbers a1<\/sub>, a2<\/sub>, . . . , an<\/sub>, S \u2208 N.
Question: Is there a subset I \u2286 {1,…,n} with \u2211 ai<\/sub> = S? <\/p>\n<\/blockquote>\n

Finding a solution for this decision problem is a very easy task in F#.<\/p>\n

let <\/span>hasSubsetSum_Naive (numbers: int list) S =\n  let rec <\/span>hasSubsetSum (a: int list) lastSum =\n    match <\/span>a with \n      <\/span>| [] -> false\n      <\/span>| x::rest -> \n        if <\/span>lastSum + x = S then\n          true\n        elif <\/span>lastSum + x > S then\n          false\n        else\n          <\/span>hasSubsetSum rest lastSum || hasSubsetSum rest (lastSum+x)\n  \n  hasSubsetSum numbers 0\n\nlet <\/span>numbers = [ 5;4;3;6;7;12 ]\nlet <\/span>searchedSum = 33  \nhasSubsetSum_Naive numbers searchedSum<\/pre>\n
Of course this small program can be easily adjusted to give the subset I back. Unfortunately this na\u00efve approach leads to a running time of O(2^n). <\/p>\n
But if S is small we can build a dynamic program<\/a> and decide the problem in O(n*S) time. <\/p>\n
 \"\" <\/p>\n
\"\" <\/p>\n
\"\" <\/p>\n
This can be easily transformed into F# code. <\/p>\n
let <\/span>hasSubsetSum (numbers: int array) S =\n   if <\/span>numbers |> Array.exists (fun <\/span>x -> <\/span>x = S) then\n     true\n   else\n     let <\/span>a = numbers |> Array.filter (fun <\/span>x -> <\/span>x < S)      \n     let <\/span>n = a.Length\n     if <\/span>n = 0 then\n       false\n     else\n       let <\/span>v = Array2.create n (S+1) 0\n       let <\/span>u = Array2.create n (S+1) false\n       let <\/span>t = Array2.create n (S+1) 0\n       \n       for <\/span>j in <\/span>[1..S] do\n         for <\/span>i in <\/span>[0..n-1] do                           \n           if <\/span>j - a.[i] >= 0 && not u.[i,j - a.[i]] then\n             <\/span>v.[i,j] <- t.[i,j - a.[i]] + a.[i]\n           if <\/span>((i = 0) || (i > 0 && t.[i-1,j] <> j)) && v.[i,j] = j then\n             <\/span>u.[i,j] <- true\n           if <\/span>v.[i,j] = j then\n             <\/span>t.[i,j] <- j\n           else\n             if <\/span>i > 0 then\n               <\/span>t.[i,j] <- max t.[i-1,j] t.[i,j-1]\n             else\n               <\/span>t.[i,j] <- t.[0,j-1]\n               \n       t.[n-1,S] = S<\/strong><\/pre>\n
https:\/\/kopapilleronline.com<\/a><\/div>\n","protected":false},"excerpt":{"rendered":"
The “Subset Sum”-problem is given as the following: SUBSET SUMInput: Numbers a1, a2, . . . , an, S \u2208 N. Question: Is there a subset I \u2286 {1,…,n} with \u2211 ai = S? Finding a solution for this decision problem is a very easy task in F#. let hasSubsetSum_Naive (numbers: int list) S = […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[23,448,8],"tags":[484,469,664,483],"_links":{"self":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/611"}],"collection":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/comments?post=611"}],"version-history":[{"count":3,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/611\/revisions"}],"predecessor-version":[{"id":2041,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/611\/revisions\/2041"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=611"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=611"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=611"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}