Problem 16.* Subset with sum S


1

Здравейте може ли някой да ми разясни този начин за решаване на задача 16 от Матрици.

Ще съм ви много благодарен . Мерси Предварително

Generate all possible sums this way: take all the numbers and mark them as "possible sum". Then take every number kok2, …, kn-1 and for each already marked "possible sum" p, mark as possible the sum p+ki. If at some step you get S, a solution is found. You can keep track of the "possible sums" either in a bool[] array possible[], where each index is a possible sum, or in a more complex data structure like Set<int>. Once you have possible[S] == true, you can find a number kisuch that possible[S-ki] == true, print ki and subtract it from S. Repeat the same to find the next kiand print and subtract is again, until S reaches 0.




Отговори



4

Това е един от най-добриете, според мен, подходи към задачата. :)

Нека вземем поредицата int[] numbers = new int[]{-2, 1, 2, 3};

Максималната сума от нея е сумата на всички положителни числа (6).

Това, на което трябва да обърнем внимание, е факта, че няма как да достъпваме число с отрицателен индекс, затова трябва да си направим една променлива offset, която да е абсолютната стойност на всички отрицателни числа (2 в случая), която при въведени само положителни числа, ще бъде 0. Така можем да достъпваме числата на позиция числто + offset-a. Целият ни масив трябва да е с дължина 9. Защо? Имаме 6 положителни позиции, една 0 и две  отрицателни ( заради -2: -1, -2).

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

bool[] possibleSums = new bool[maxPositiveSum(сумата на всички положителни числа)+1 (заради 0) + offset(сумата на отриателни числа)]; //дефолтната стойност на всички елементи е false

Можем да кажем, че сборът на 0 числа от масива прави сума 0, затова на позиция 0+offset или просто offset посочваме, че имаме възможна сума.

possibleSums[offset] = true;

След това обхождаме всички числа от масива numbers и задаваме стойност true на всеки индекс, който е възможна сума + настоящата сума: ВИЖ ТУК

[0] [1] [2] [3] [4] [5] [6] [7] [8] // индекси

-2  -1   0   1    2   3    4   5    6 //стойността на числата - offset

 F    F    T   F    F   F    F    F    F // T-true, F-false

При -2 обхождаме всички стойности, единствено 0 ни е true, затова на позиция index+number (2 + -2) задаваме true;

[0] [1] [2] [3] [4] [5] [6] [7] [8] // индекси

-2  -1   0   1    2   3    4   5    6 //стойността на числата - offset

 T    F    T   F    F   F    F    F    F // T-true, F-false

След това имаме 1. Тъй като числото е положително, обхождаме булевия масив от последен към първи индекс, за да не допуснем грешки при добавянето на числа. Имаме 2 true позиции = [0](-2)  и [2](0), като за всякато от тях на съответната позиция + настоящото число посочваме, че сумата е възможна:

[0] [1] [2] [3] [4] [5] [6] [7] [8] // индекси

-2  -1   0   1    2   3    4   5    6 //стойността на числата - offset

 T    Т    T   Т    F   F    F    F    F // T-true, F-false

...и така нататък, докато минем по всички числа и открием всички възможни суми. :)

В зависимост от това дали числото е положително или отрицателно, трябва да обхождаме масива possibleSums по различен начин, защото иначе ще добавяме едно число повече от веднъж и ще получаваме грешни резултати.

С това изичсляването на възможните суми приключва.

Трябва да направим проверка дали сумата е възможна преди да проверим дали съществува. Ако имаме търсена сума int sum = 6; трябва първо да видим дали имаме такъв индекс:

if (sum < -offset || sum > maxPositiveSum)

{

    Console.WriteLine("Impossible sum");

}

в противен случай ще проверим дали сумата е възможна:

else

{

    if (possibleSum[sum + offset])

    {

        Console.WriteLine("Yes");

    }

    else

    {

        Console.WriteLine("No");

    }

} // :)


от dentia (12519 точки)


2

Трябва да го прочета няколко пъти .... 

Благодарско за Обяснението :)


от slavib (176 точки)


3

Можеш да погледнеш решението ми ,което работи с много полезно свойство на двоичните числа - да открием всички възможни комбинации между числа от масива и съответно тяхната сума . Взимаме само тези числа към текущия сбор,чиито индекси отговарят на индексите само на единиците '1' от двуичното число  .

Можеш да погледнеш кода ми за решаване на задачата на около 30 реда с обяснения ТУК , а ако поразчистя още малко може и на 20 да се събере :)


от IvayloAndonov (1994 точки)


2

Да, това решение е готино и сравнително лесно за разбиране. Единственият проблем е, че е решение за много ограничен брой елементи.

Иначе вариант е и да извъртиш всички комбинации от числа. :)


от dentia (12519 точки)

0
А какъв е смисъла да почваш от i=0 ? всяка маска с 0 е пак толкова

от kiko81 (1655 точки)


4
Ето тук е обяснен проблема с техниката "Динамично оптимиране": CLICK

от ivaylo.kenov (30760 точки)


0

Еййй Много Благодарско :)


от slavib (176 точки)