# PBinfo #1959 – Rucsac_Halloween – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

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.

## Cod sursă C++

```cpp
///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;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1959)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1959/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1959/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)