Difference between revisions of "TADM2E 3.12"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
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 subset existing and we can go on:
+
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
 
# R:=S
 
# for i:=1 to n do
 
# for i:=1 to n do
## If &lt;math&gt;bb(R/\{x_i\})&lt;/math&gt; is True then &lt;math&gt;R:=R/\{x_i\}&lt;/math&gt;
+
## If <math>bb(R/\{x_i\})</math> is True then <math>R:=R/\{x_i\}</math>
 
When this iteration is finished R will be subset of S that adds up to k.
 
When this iteration is finished R will be subset of S that adds up to k.
 +
 +
This above solution assumes that there is only a single subset of S that adds to k.

Latest revision as of 21:37, 24 January 2019

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

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

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

This above solution assumes that there is only a single subset of S that adds to k.