Rezolvare completă PbInfo #1959 Rucsac_Halloween

Cerința

Sabin merge la colindat de Halloween. Ştiind ca poate colinda la n case, iar la fiecare primeşte g[1], g[2], ..., g[n] bomboane, iar în rucsacul lui încap G bomboane, aflaţi numărul minim de case pe care trebuie să le colinde Sabin pentru a umple ghiozdanul.

Date de intrare

Programul citeşte de la tastatură numerele n, G şi numerele g[1], g[2], ..., g[n].

Date de ieșire

Programul va afișa pe ecran numărul de case. Dacă nu poate să umple ghiozdanul, se va afişa mesajul NU.

Restricții și precizări

  • 1 ≤ n ≤ 1000
  • 0 ≤ G ≤ 10000
  • 1 ≤ g[1], g[2], ..., g[n] ≤ G

Exemplu

Intrare

5 8
1 2 7 3 4

Ieșire

2

Explicație

Sabin poate colinda la casele 1 şi 3 pentru a umple ghiozdanul.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Rucsac_Halloween:

///Solutie - Moca Andrei - 100p
#include <iostream>
using namespace std;
const int Inf = 0x3f3f3f3f;
int n, k, G, g[1002], nr[100002];
void Halloween();
int main()
{
    cin >> n >> G;
    for (int i = 1; i <= G; i++)
        nr[i] = Inf;
    for (int i = 1; i <= n; ++i)
        cin >> g[i];
    Halloween();
    if (nr[G] < Inf)
        cout << nr[G];
    else
        cout << "NU";
}
void Halloween()
{
    nr[0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = G - g[i]; j >= 0; --j)
            if (nr[j] != Inf && nr[j + g[i]] > nr[j] + 1)
                nr[j + g[i]] = nr[j] + 1;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1959 Rucsac_Halloween

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1959 Rucsac_Halloween de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!