Problema C++ [v2]

[mirrorer]

Enunt:

Se dau N tipuri de bancnote de valori b1,b2,b3,..bn.Din fiecare tip se dispune un numar nelimitat de bancnote.

Se defineste pentru un subset de tipuri de monede, sa-l numim X, capacitatea de acoperire a acestuia ca fiind numarul de sume cuprinse intre 1 si S (inclusiv) pe care le poate obtine folosind numai monede de tipuri aflate in subsetul X.

Se cere:

Fiind data S(o suma de bani ) , se cere suma capacitatilor de acoperire a tutoror subseturilor de monede posibile .

Restrictii:

1. N<=17

2. S<=512

Exemplu:

Pentru n=2 , bancontele de b1=2 b2=3 si S=10 lei ,trebuie sa afiseze : 17

Explicatie :

Cu subsetul {2} se pot obtine 5 sume: 2, 4, 6, 8, 10

Cu subsetul {3} se pot obtine 3 sume: 3, 6, 9

Cu subsetul {2,3} se pot obtine 9 sume: 2, 3, 4, 5, 6, 7, 8, 9, 10

Observati ca nu e obligatoriu ca toate tipurile de bancnote dintr-un subset sa fie folosite: de?exemplu suma 6 pentru ultimul subset se obtine folosind numai monede de tip “2” sau numai monede de tip “3” (daca le folosim pe amandoua nu putem obtine suma 6).

Numarul cautat va fi astfel 5+3+9=17.

Nu va pun acum sa implementati la ora asta , ci doar sa-mi spuneti o idee de rezolvare si complexitatea acesteia.

Credit : @danyweb09 ( Problema initiala )

[MARIUSCS]

Cu subsetul {2, 3} nu ar trebui sa se obtina 2, 3, 4, 6, 8, 9, 10?As vrea as incerc sa rezolv problema dar nu inteleg de ce ai scris 2, 3, 4, 5, 6, 7, 8, 9, 10 acolo.

[bcman]

Cu subsetul {2, 3} nu ar trebui sa se obtina 2, 3, 4, 6, 8, 9, 10?As vrea as incerc sa rezolv problema dar nu inteleg de ce ai scris 2, 3, 4, 5, 6, 7, 8, 9, 10 acolo.

4 = 2+2

5 = 2+3

6 = 3 +3

7 = 2 + 2 + 3

8 = 2 + 2 + 2 + 2

9 = 3 + 3 + 3

[mirrorer]

Inca astept idei

[MARIUSCS]

Ma cam depaseste...nu prea stiu cum as putea calcula de exemplu pentru 7=2+2+3

Sigur e ceva simplu, dar cand nu ai idei, nu ai idei...sunt foarte curios sa vad care va fi algoritmul.

[mirrorer]

Nu e chiar atat de simplu ..

[MARIUSCS]

Nu a rezolvat nimeni pana acum?Sunt curios cum trebuie gandita problema

[sevenziparchive]

daca se cere doar suma capacitatilor pt toate subseturile posibile, practic trebuie sa lucrezi cu div si mod.

in primul rand, fiecare dintre b1 .. bn este de sine statator un subset, asa ca avem cel putin s div b1 + s div b2 ... s div bn posibilitati.

mai departe, o functie probabil recursiva, ceva de genul (s - 1 x b1) div b2 o rezolvare, (s - 2 x b1) div b2 a 2-a rezolvare... (s mod bn) mod bn-1) ... mod b2) div b1 cred ca ar fi ultima rezolvare.

asta e ideea mea, poate am inteles problema gresit. nu o sa stau sa programez, dar sunt curios daca e buna.