[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




Отговори



1
Това е моето решение: http://pastebin.com/2rc1WGpW
Искам да попитам всички подмножества ли трябва да се изкарат, понеже в условието не е зададено. Моето решение намира 1 или няколко случая (не всичките).

от teleriknetwork (2734 точки)


0
Според мен трябва да изкара всички множества с такава сума. Но зависи как го интерпретираш условието, защото не е достатъчно обяснено.

от Hristo.B (3885 точки)

0
Според мен в условието се иска едно, но нищо не пречи да се изкарат и всички. Вероятно ще трябва само да не си спреш програмата след като изкараш първото : )

от stanev.plamen (1143 точки)


1

Ето и две решения и от мен:

http://pastebin.com/Ce96Tqcv - рекурсия

http://pastebin.com/2JrP5KNB - побитово

Подхода и при двете решения е подобен. Генерират се еденици и нули - с рекурсия или побитово. Така се правят всички възможни комбинации от единици. За всяка една комбинация където имаме 1 - взимаме числото от масива, накрая на итерацията сравняваме сумата - ако съвпада принтваме съответните числа.


от stanev.plamen (1143 точки)


0

Колеги, някъде имаше видео, в което Ники обяснява решението на задачата с динамично оптимиране, а НЕ побитово. Някой може ли да даде линк? Побитовото ми е ясно и съм си я решил така, но не ми е ясна идеята на динамичното. В книгата на Наков задачата е 20-та от Масиви и упътването ми се вижда, меко казано, неразбирамо и безполезно, колкото да го има. На предишната страница потребителят no_name е дал горе-долу насока какво се прави, но нито разбрах ЗАЩО, нито разбрах как ще се изпълни условието dp[j - arr[i]] == true за dp[S], като от S започваме, и като всички стойности на dp[] са false по default. Не ми е ясна цялостната идея, какво се цели, какви са тези "възможни" суми? А кои са невъзможни тогава?


от varbanoff (2325 точки)


0
Принципно това е видеото на Ники за Масиви, http://www.youtube.com/watch?v=JQmmpK_CaTA а има допълнителна информация в блога си http://nikolay.it/index.html обаче мисля че и това видео на Наков за Динамично оптимиране може да ти помогне, виж от 1.24.00 нататък, даже си пише заглавие на задачата, дано съм ти бил полезен :) http://www.youtube.com/watch?v=2_9nIEETso8

от tsonko_genov (708 точки)


0

И тук добавям още едно решение по метода Динамично оптимиране, защото няма много такива в темата, а с този алгоритъм програмата работи много бързо и не е проблем да сметне веднага валидните суми на масив от над 50 елемента. По-подробно как работи програмата е обяснено тук:

Задачата на C++ е в демотата към курса: тук

Особеното в началото е че заделяме ръчно offset, който трябва да е по-голям от броя на предполагаемите суми и най-големия елемент по модул.

След това правим два масива – един в който ще записваме всички суми и един при който записваме сумите при текущата итерация.

Започваме от първия елемент, проверяваме дали има предходни получени суми – ако да – събираме го с всяка сума и резултата го добавяме към валидните суми. Накрая на текущата итерация добавяме самия елемент като валидна сума.  Правим тази операция за всеки един елемент и получаваме всички възможни суми.

Интересното е че за да не хабим излишно време в смятане на нули – пазим първия и последния индекс в които имаме реални решения (суми).

Също много интересно е как работи програмата за отрицателните числа като ги записва по индекс като самото число + offset-a. Затова offset-a трябва да е по-голям от най-големия модул на елемент.

Като минус на този алгоритъм може да се отчете че не може да хване и принтира всички възможни комбинации от елементи които участват в дадена сума и съответно точния брой такива суми – поради това че смята с по-малко итерации.

решение: http://pastebin.com/8KbAt121


от stanev.plamen (1143 точки)


0

GitHub

Рекурсивно решение. Първо пробва комбинация от 1 елемент, после 2 3 .... колкото елементи има масива . В самото пробване се генерира вектор с големина броя на елементите които сме решили да пробваме - и с един масив от булеви променливи (все пак може да използваме всяка цифра само веднъж) се проверява дали всяка цифра е вече използвана. Ако не е викаме рекурсия за следващата позиция в вектора . Всеки път се проверява дали конкретната сума не е търсената или по-голяма - ако е се прекратява търсенето. Като се достигне размера на вектора се проверява пак - ако сумата от елементите не е търсената се пробва отново.


от dzhenko (3893 точки)


0
Ето и моето решение, ако някой има препоръки да ги сподели
http://pastebin.com/EHaMAbWX

от MarinPetrov (158 точки)


0

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