[C#] Arrays - 16 задача


4

Условие:

16.* We are given an array of integers and a number S. Write a program to find if there exists a subset of the elements of the array that has a sum S. Example:

  arr={2, 1, 2, 4, 3, 5, 2, 6}, S=14 -> yes (1+2+5+6)

Мое решение:

http://pastebin.com/3yBtrr6B




Отговори



28

Решение:

http://pastebin.com/gMUCEvZz

Обяснение:

В основата на това решение, стои решението на задачата за намиране на броя на подмножествата от Примерния изпит за първата част на курса, обяснена на моята група от Николай Костов при подготовката ни за изпит ( Видео от лекцията: http://www.youtube.com/watch?v=Sk0PX0YSHtk  ).

Ето в общи линии в какво се състой решението на задачата:

1. Попълваме си в един масив всички елементи.

2. Определяме максимални брой на подмножествата по формулата - 2 на степен броя на елементите ( тук взимаме в предивид и нулевото множество ).

3. И сега идва ядрото на задачата - как да определим кой са нашите подмножества. В общи лини, това става чрез побитовата репрезентация на числата от 0 до броя на всички възможни подмножества.

Ще ви покажа с пример как може да видим всички подмножества на елементите 1, 2, 3, 4. Всички възможно подмножества тук са - 15.

SubSetSum

Т.е. на всяка единица съответства елемнт от всички елементи.

4. Реализацията в задачата - с първия for цикъл обхождаме всички възможно комбинация в задачата, а със втория - всички елементи в масива. С помоща на побитови операция проверяваме следното - 0 бит от първия цикъл 1 или нула е ? Ако е 1 взимамем елмента и го добавяме към общата сума, ако не го игнорираме. Същото става и за 1вия бит - ако е 0 го игнорираме, ако не е прибавяме елемента с индекс 1 към текущия сбор.

5. Текущата редичка си я съхраняваме в обикновен стринг ( със StringBuilder е по-добре, но тук използвах конкитенация )

6. И последната порверка е дали текущата сума е равна на търсената сума - ако това е вярно, я изписваме на конзолата.

Забележка: При всяка проверка на възможна комбинация трябва да изпразваме string - a където държим редичката си.


от Teodor92 (13062 точки)


0
Евала, Теди!

от anonymous (0 точки)

0
Много добре бих казал и доста полезно помогна ми да реша задачата.. да не кажа изкопирам Ето и моя вариант само дето вместо в стринг си пазя елементите от подмножеството в List и ако е равно на търсеното подмножество добавям List-a в друг List ..ако ли не чистя колекцията
https://github.com/martinivanovit/SimpleProjects/blob/master/SubsetSum

от Mahata231 (1351 точки)



0
Ето и моето решение при повечето стойностти на sum работи, но при sum = 13 примерно смята до 12 .
http://pastebin.com/EJnd5Ygu

от iwitass (3695 точки)


1
Ето моето решение http://pastebin.com/3rUkCEpP
използвам зависимостта между бинарната репрезентация на номера на подмножеството и позицията на елемента в масива обяснена по горе много добре от колегата и записвам елементите на подмножеството със stringbuilder



0
Няма нужда да подготвяш за печат всяка една комбинация и след това да я затриваш. Печатай само при съвпадение на текущата и търсената сума. Информацията за комбинацията я имаш в "i", просто трябва да завъртиш наново вътрешния цикъл и да изведеш резултата.

от pirin (1101 точки)


3

Ето и моето решение: source.


от jasssonpet (6814 точки)


2

http://pastebin.com/DicSfm7M

 

Това е моето решение. До голяма степен се основава на обяснението, което Теодор Куртев е представил.
 
Разликата е единствено в това, че не използвам побитовите операции, които той използва в решението си, а представям всички възможни комбинации на числата от 1 до N-та степен на двойката(N= arr.Length) с Char масиви всеки път, което сигурно е по-бавно (налучквам), но пък си работи ефикасно.
На таблицата, която колегата е постнал се вижда ясно бинарното представяне на числата от 0 до... 2^n-1. 
В моето решение тези числа всеки път се пазят в този Char-масив (понеже това са всички възможни комбинации) в даден момент единиците попадат на позициите, на които са числата, които ни трябват ,сумират се и сумата съответно е равна на търсена.
Не се разбира много от обяснението, ама горе - долу да се ориентирате, ако случайно се зачуди някой за нещо.

от boncho.vylkov (1923 точки)


0
http://pastebin.com/DicSfm7M

от boncho.vylkov (1923 точки)


0
Също с бинарния метод, аз само ги извеждам без стрингове.
http://pastebin.com/5Y1xRkjg

от spareva (1375 точки)


2
http://pastebin.com/cAd6LAGp
В решението са обяснителните коментари - уви няма как да се избяга от генерирането на комбинации с битове :)

от shristoff (747 точки)


3
Ето едно решение без бинарни операции.
И без да предварително изкарване на всички комбинации.
http://pastebin.com/CB80UbXh



2

А ето и едно решение с рекусивен метод.

Решение


от nikola76 (1250 точки)


0

И от мен едно решение с побитовите комбинации и извеждане на всички интервали, които имат търсената сума.

http://pastebin.com/cB8PV1r9


от sylviapsh (302 точки)