Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Here is my algorithm. It runs in <code>O(2^(n/2))</code> and solves <code>SubsetSum(1000, list-of-1000-ones)</code> in 20 milliseconds. See the comments at the end of IVlad's post.</p> <pre><code>using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; namespace SubsetSum { class Program { static void Main(string[] args) { var ns = new List&lt;int&gt;(); for (int i = 0; i &lt; 1000; i++) ns.Add(1); var s1 = Stopwatch.StartNew(); bool result = SubsetSum(ns, 1000); s1.Stop(); Console.WriteLine(result); Console.WriteLine(s1.Elapsed); Console.Read(); } static bool SubsetSum(ist&lt;int&gt; nums, int targetL) { var left = new List&lt;int&gt; { 0 }; var right = new List&lt;int&gt; { 0 }; foreach (var n in nums) { if (left.Count &lt; right.Count) left = Insert(n, left); else right = Insert(n, right); } int lefti = 0, righti = right.Count - 1; while (lefti &lt; left.Count &amp;&amp; righti &gt;= 0) { int s = left[lefti] + right[righti]; if (s &lt; target) lefti++; else if (s &gt; target) righti--; else return true; } return false; } static List&lt;int&gt; Insert(int num, List&lt;int&gt; nums) { var result = new List&lt;int&gt;(); int lefti = 0, left = nums[0]+num; for (var righti = 0; righti &lt; nums.Count; righti++) { int right = nums[righti]; while (left &lt; right) { result.Add(left); left = nums[++lefti] + num; } if (right != left) result.Add(right); } while (lefti &lt; nums.Count) result.Add(nums[lefti++] + num); return result; } } } </code></pre> <p>And here is an improved version that prunes the sets:</p> <pre><code>static bool SubsetSum(List&lt;int&gt; nums, int target) { var remainingSum = nums.Sum(); var left = new List&lt;int&gt; { 0 }; var right = new List&lt;int&gt; { 0 }; foreach (var n in nums) { if (left.Count == 0 || right.Count == 0) return false; remainingSum -= n; if (left.Count &lt; right.Count) left = Insert(n, left, target - remainingSum - right.Last(), target); else right = Insert(n, right, target - remainingSum - left.Last(), target); } int lefti = 0, righti = right.Count - 1; while (lefti &lt; left.Count &amp;&amp; righti &gt;= 0) { int s = left[lefti] + right[righti]; if (s &lt; target) lefti++; else if (s &gt; target) righti--; else return true; } return false; } static List&lt;int&gt; Insert(int num, List&lt;int&gt; nums, int min, int max) { var result = new List&lt;int&gt;(); int lefti = 0, left = nums[0]+num; for (var righti = 0; righti &lt; nums.Count; righti++) { int right = nums[righti]; while (left &lt; right) { if (min &lt;= left &amp;&amp; left &lt;= max) result.Add(left); left = nums[++lefti] + num; } if (right != left &amp;&amp; min &lt;= right &amp;&amp; right &lt;= max) result.Add(right); } while (lefti &lt; nums.Count) { left = nums[lefti++] + num; if (min &lt;= left &amp;&amp; left &lt;= max) result.Add(left); } return result; } </code></pre> <p>This last one solved the problem with 100000 ones in about 5 milliseconds (but this is a best case of the algorithm, with real world data it will be slower).</p> <p>For your use this algorithm is probably fast enough (and I don't see any obvious improvements). If you enter 10,000 products with a random price between 0 and 20 and your goal is to sum to 500 this is solved in 0.04 seconds on my laptop.</p> <p>Edit: I just read on Wikipedia that the best known algorithm is <code>O(2^(n/2)*n)</code>. This one is <code>O(2^(n/2))</code>. Do I get the Turing Award?</p>
    singulars
    1. This table or related slice is empty.
    1. POSubset sum problem
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJules
    1. USJules
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThanks, Nice effort :)
      singulars
      1. PO
      1. USMadBoy
    2. COWhy do you say it's `O(2^(n/2))`? You traverse your entire `nums` list in each call to `Insert`. I think it's pointless to do such tests really, because it's easy to find one that each algorithm (pseudopolynomial or exponential) will fail one. You found one that the pseduopolynomial algo fails on (takes a long time on): 100000. Here's one that your algo takes a long time on too: 10000 numbers: 1 2 3 4 ... 10000. Search for 345600. Also, you're only printing true or false, I think printing the numbers too will add some overhead as well. Anyway, this does seem faster than the DP so +1, however..
      singulars
      1. PO
      1. USIVlad
    3. COHowever, if we're going to battle with such high numbers, let me implement my randomized algorithm when I get back from college :). I think that is better if we're dealing with very high numbers.
      singulars
      1. PO
      1. USIVlad
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload