{"id":1937,"date":"2024-03-28T01:14:05","date_gmt":"2024-03-28T00:14:05","guid":{"rendered":"https:\/\/es-andreabianchini.it\/andrewsblog\/?p=1937"},"modified":"2024-03-30T05:05:13","modified_gmt":"2024-03-30T04:05:13","slug":"an-exact-algorithm-of-polynomial-complexity-for-the-subset-sum-problem","status":"publish","type":"post","link":"https:\/\/es-andreabianchini.it\/andrewsblog\/?p=1937","title":{"rendered":"An Exact Algorithm of Polynomial Complexity for the Subset Sum Problem"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code># ssp.py - An Exact Algorithm of Polynomial Complexity for the Subset Sum Problem\n#\n# Andrea Bianchini, 2024, Common Creative CC BY-NC 4.0. \n#\n# see also https:\/\/es-andreabianchini.it\/ssp_eng.pdf\n#\n\nfrom random import randrange\nimport math\n\ntry:\n    inp = open(\"input.txt\",\"rt\")\n    n=int(inp.readline())\n    c=int(inp.readline())\n    wmin=int(inp.readline())\n    wmax=int(inp.readline())\n    inp.close()\n    w=sorted(&#91;int(wmin+randrange(wmax-wmin)) for i in range(n)])\n    c1=&#91;0 for i in range(n)]\n    sol=&#91;0 for i in range(n)]\n    bestsolu=&#91;0 for i in range(n)]    \n    niter=0\n    bestsol=0\n    bestsolk=0\n\nexcept Exception:\n    print(Exception)\n    print()\n    print(\"ssp, Andrea Bianchini, 2024, Common Creative CC BY-NC 4.0.\")\n    print(\"USAGE:\")\n    print(\"ssp\")\n    print(\"ssp reads input data from input.txt\")\n    print(\"WHERE input.txt is in the form:\")\n    print(\"n     # number of items\")\n    print(\"c     # capacity of the knapsack\")\n    print(\"wmin  # min item's weight\")\n    print(\"wmax  # max item's weight\")\n    print()\n    \ndef solve():\n    global n\n    global c\n    global w\n    global bestsolu\n    global sol\n    global bestsol\n        \n        \n    bestsol=0\n    solvalue=0\n    divi=1\n    T=int(pow(2,n-1))\n    while(T>1 and bestsol&lt;c):\n        t=0\n        divi=1\n        while(divi&lt;int(pow(2,n)) and bestsol&lt;c):\n\n            #print(bin(T),bin(t),bestsol)\n\n\n            sol=list(map(int,bin(t+int(T\/divi))&#91;2:].zfill(n)&#91;::-1]))\n            gt=sum(&#91;sol&#91;i]*w&#91;i] for i in range(n)])\n            if (gt&lt;=c):\n                t=t+int(T\/divi)\n\n            divi*=2\n            \n            solvalue=gt\n            if (bestsol&lt;solvalue and solvalue&lt;=c):\n                bestsolu=list(map(int,bin(t)&#91;2:].zfill(n)&#91;::-1]))\n                bestsol=solvalue\n\n        T=int(T\/2)\n                   \n    return\n\ntry:\n    while(True):\n        w=sorted(&#91;int(wmin+randrange(wmax-wmin)) for i in range(n)])\n        \n        print(\"n=\"+str(n))\n        print(\"c=\"+str(c))\n        print(\"wmin=\"+str(wmin))\n        print(\"wmax=\"+str(wmax))\n        print(\"w = \",w)\n        print()\n\n        bestsol=0\n        \n        solve()\n    \n        solvalue=sum(&#91;bestsolu&#91;i]*w&#91;i] for i in range(n)])\n\n        print()\n        print(\"Solution=\"+str(solvalue))\n        print(\"Sol. Vector = \",bestsolu)\n        print(\"Sol. Items = \",&#91;w&#91;i] for i in range(n) if bestsolu&#91;i]==1])\n        print(\"Hit return...\")\n        input()\nexcept Exception:\n    print(Exception.message)<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">input.txt file example:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>50\n10000\n200\n4000<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Execution example:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>n=50\nc=10000\nwmin=200\nwmax=4000\nw =  &#91;257, 537, 580, 580, 664, 671, 688, 755, 844, 939, 953, 960, 1014, 1095, 1250, 1359, 1417, 1463, 1513, 1527, 1575, 1629, 1737, 1738, 1817, 1841, 1935, 1942, 2115, 2240, 2318, 2330, 2565, 2606, 2681, 2692, 2788, 3075, 3112, 3196, 3201, 3230, 3257, 3368, 3400, 3440, 3508, 3512, 3782, 3938]\n\n\nSolution=10000\nSol. Vector =  &#91;1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\nSol. Items =  &#91;257, 580, 580, 664, 671, 688, 755, 844, 939, 953, 960, 1014, 1095]\nHit return...\n\nn=50\nc=10000\nwmin=200\nwmax=4000\nw =  &#91;293, 419, 439, 576, 635, 672, 978, 1031, 1063, 1120, 1229, 1285, 1288, 1446, 1660, 1800, 1978, 2014, 2033, 2034, 2040, 2148, 2185, 2193, 2201, 2479, 2506, 2521, 2540, 2553, 2585, 2673, 2799, 2976, 3051, 3089, 3287, 3371, 3379, 3390, 3438, 3581, 3613, 3661, 3696, 3753, 3763, 3766, 3834, 3836]\n\n\nSolution=10000\nSol. Vector =  &#91;1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\nSol. Items =  &#91;293, 2201, 2479, 2506, 2521]\nHit return...\n<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><a href=\"https:\/\/es-andreabianchini.it\/ssp_eng.pdf\" target=\"_blank\" rel=\"noreferrer noopener\">https:\/\/es-andreabianchini.it\/ssp_eng.pdf<\/a><\/p>\n\n\n\n<p class=\"has-text-align-right wp-block-paragraph\"><strong><em>Andrea Bianchini 2024.<\/em><\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"<p>input.txt file example: Execution example: https:\/\/es-andreabianchini.it\/ssp_eng.pdf Andrea Bianchini 2024.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12,11,7],"tags":[],"class_list":["post-1937","post","type-post","status-publish","format-standard","hentry","category-python","category-or","category-stem"],"_links":{"self":[{"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=\/wp\/v2\/posts\/1937","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1937"}],"version-history":[{"count":7,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=\/wp\/v2\/posts\/1937\/revisions"}],"predecessor-version":[{"id":1949,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=\/wp\/v2\/posts\/1937\/revisions\/1949"}],"wp:attachment":[{"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1937"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1937"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1937"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}