Difference between revisions of "3.27"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
(Created page with "Let's put into the black box whole set <math>S=\{x_i\}_{i=1}^n</math>. If <math>bb(S)</math> is True, then such a subset exists and we can go on: # R:=S # for i:=1 to n do ##...")
 
(Created page with "Let's put into the black box whole set <math>S=\{x_i\}_{i=1}^n</math>. If <math>bb(S)</math> is True, then such a subset exists and we can go on: # R:=S # for i:=1 to n do ##...")
 
(No difference)

Latest revision as of 18:06, 20 September 2020

Let's put into the black box whole set [math]\displaystyle{ S=\{x_i\}_{i=1}^n }[/math]. If [math]\displaystyle{ bb(S) }[/math] is True, then such a subset exists and we can go on:

  1. R:=S
  2. for i:=1 to n do
    1. If [math]\displaystyle{ bb(R/\{x_i\}) }[/math] is True then [math]\displaystyle{ R:=R/\{x_i\} }[/math]

When this iteration is finished R will be subset of S that adds up to k.

Above solution works even when there are multiple subsets that add up to k.


Back to Chapter 3