Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The brute-force idea is easy:</p> <ol> <li>Generate all possible subsets of your 20 items, saving only those which satisfy your weight constraint. If you want to be fancy, you can even only consider subsets to which you cannot add anything else without violating the weight constraint, since only these can possibly be the right answer. O(2^n)</li> <li>Find the subset with maximum weight. linear in terms of the number of candidates, and since we have O(2^n) candidates, this is O(2^n).</li> </ol> <p>Please comment if you'd like some pseudocode.</p> <p>EDIT: What the hey, here's the pseudocode just in case.</p> <pre><code> GetCandidateSubsets(items[1..N], buffer, maxw) 1. addedSomething = false 2. for i = 1 to N do 3. if not buffer.contains(item[i]) and weight(buffer) + weight(items[i]) &lt;= maxw then 4. add items[i] to buffer 5. GetCandidateSubsets(items[1..N], buffer) 6. remove items[i] from buffer 7. addedSomething = true 8. if not addedSomething then 9. emit &amp; store buffer </code></pre> <p>Note that the GetCandidateSubsets function is not very efficient, even for a brute force implementation. Thanks to amit for pointing that out. You could rework this to only walk the combinations, rather than the permutations, of the item set, as a first-pass optimization. </p> <pre><code> GetMaximalCandidate(candidates[1..M]) 1. if M = 0 then return Null 2. else then 3. maxel = candidates[1] 4. for i = 2 to M do 5. if weight(candidates[i]) &gt; weight(maxel) then 6. maxel = candidates[i] 7. return maxel </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POBrute force implementation for 0-1 Knapsack
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USPatrick87
    1. USPatrick87
    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. CO(1) finding maximum weight is `O(2^n)` as well, since you need to check all subsets. (2) the main advantage of backtracking and bruteforce is usually space complexity, by storing all possibilities, your space complexity is `O(2^n)` and you lose this advantage. (3) the solution in your pseudocode is not `O(2^n)`, it is `O(n!)`, or even `O(n^n)`
      singulars
      1. PO
      1. USamit
    2. CO@amit: Right, getting the maximum element would be O(2^n) since there are O(2^n) subsets to check and the maximum-element-finding code looks at them all. The second criticism isn't all that meaningful to me, since the OP doesn't really indicate this is a concern. The criticism in (3) is noted; for what it's worth, I didn't put a lot of work into this code.
      singulars
      1. PO
      1. USPatrick87
    3. COhi note that if subset A has 1000 values and 523 weights and B has 999 values and 524 weights then A must be optimal solution
      singulars
      1. PO
      1. USMinhHoang
 

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