# include < iostream >
# include < cstring >
using namespace std ;
const int MAX_N = 100 ;
int n, L, a[MAX_N], sol[MAX_N], available [MAX_N];
// Returneaza true daca exista o solutie valida
bool solveBT ( int len ) {
if ( len == L) {
return true ;
}
for ( int i = 0 ; i < n; i++) {
if ( available [i] > 0 && len + a[i] <= L) {
sol[ len ] = a[i];
available [i]--;
if ( solveBT ( len + a[i])) {
return true ;
}
available [i]++;
}
}
return false ;
}
int main () {
cout << " Introduceti numarul de bucati de teava : " ;
cin >> n;
cout << " Introduceti lungimea țevii: " ;
cin >> L;
cout << " Introduceti lungimile bucăților de țeavă disponibile: " ;
for ( int i = 0 ; i < n; i++) {
cin >> a[i];
available [i] = 1 ;
}
if ( solveBT ( 0 )) {
cout << " Solutia gasita este: " ;
for ( int i = 0 ; i < L; i++) {
cout << sol[i] << " " ;
}
cout << endl ;
} else {
cout << "Nu exista solutie !" << endl ;
}
return 0 ;
}
Metoda programării dinamice: Pentru a folosi metoda programării dinamice, vom crea un vector dp [] în care dp [i] reprezintă numărul de bucăți de țeavă necesare pentru a construi o țeavă de lungime i. Vom parcurge lungimile de la 1 la L și vom calcula dp [i] prin parcurgerea tuturor bucăților de țeavă disponibile și încercarea de a le folosi pentru a ajunge la lungimea i. Pentru fiecare bucățică de țeavă disponibilă, vom verifica dacă putem ajunge la lungimea i cu ea. Dacă da, vom încerca să construim un nou lanț prin adăugarea bucății curente la un lanț anterior de lungime i - lungimea bucății curente. Dacă noul lanț este mai bun decât cel precedent, îl vom actualiza.
De exemplu, să presupunem că avem următoarele bucăți de țeavă disponibile: 1, 2 și 5, și că vrem să construim o țeavă de lungimea 7. Vom parcurge lungimile de la 1 la 7 și vom calcula dp [i]. Pentru dp [1], putem folosi bucata de țeavă de lungime 1, deci dp [1] va fi 1. Pentru dp [2], putem folosi bucata de țeavă de lungime 2, deci dp [2] va fi 1 (folosim o bucată de țeavă de lungime 2 și o bucată de țeavă de lungime 1). Pentru dp [3], nu putem folosi nicio bucată de țeavă disponibilă, deci dp [3] va fi 0. Pentru dp [4], putem folosi bucata de țeavă de lungime 2, deci dp [4] va fi 2 (folosim o bucată de țeavă de lungime 2 și două bucăți de țeavă de lungime 1). Pentru dp [5], putem folosi bucata de țeavă de lungime 5, deci dp [5] va fi 1 (folosim o bucată de țeavă de lungime 5). Pentru dp [6], putem folosi bucata de țeavă de lungime 2, deci dp [6] va fi 2 (folosim o bucată de țeavă de lungime 2 și trei bucăți de țeavă de lungime 1). Pentru dp [7], putem folosi bucata de țeavă de lungime 2 sau bucata de țeavă de lungime 5. Dacă folosim bucata de țeavă de lungime 2, dp [7] va fi 3 (folosim o bucată de țeavă de lungime 2, o bucată de țeavă de lungime 5 și două bucăți de țeavă de lungime 1). Dacă folosim bucata de țeavă de lungime 5, dp [7] va fi 2 (folosim o bucată de țeavă de lungime 5 și două bucăți de țeavă de lungime 1). Deci soluția este dp [7] = 2.
Pentru a implementa această metodă în C++, vom utiliza un vector de dimensiune L+ 1 pentru stocarea valorilor dp . Vom inițializa toate elementele cu valoarea 0, cu excepția primului element, dp [0], care va fi inițializat cu valoarea 1 pentru a indica că putem construi o țeavă cu lungimea 0 folosind o singură bucată de țeavă cu lungimea 0.
Apoi, vom parcurge lungimile de la 1 la L și vom calcula dp [i] prin parcurgerea tuturor bucăților de țeavă disponibile și verificarea dacă putem folosi bucata respectivă pentru a construi o țeavă de lungime i. Dacă putem, actualizăm valoarea dp [i] cu dp [i-a[j]].
În final, valoarea dp [L] va fi soluția problemei noastre, adică numărul de modalități de a construi o țeavă de lungime L folosind bucăți de țeavă de lungimi a.
Mai jos este prezentat un exemplu de implementare a acestei metode
# include < iostream >
using namespace std ;
const int MAX_N = 100 ;
int a[MAX_N], dp [MAX_N];
int main () {
int n, L;
cout << " Introduceti numarul de bucati de teava disponibile: " ;
cin >> n;
cout << " Introduceti lungimea dorita pentru teava : " ;
cin >> L;
cout << " Introduceti lungimile bucatilor de teava disponibile: " ;
for ( int i = 0 ; i < n; i++) {
cin >> a[i];
}
dp [ 0 ] = 1 ;
for ( int i = 1 ; i <= L; i++) {
dp [i] = 0 ;
for ( int j = 0 ; j < n; j++) {
if (i >= a[j]) {
dp [i] += dp [i-a[j]];
}
}
}
cout << " Numarul de modalitati de a construi o teava de lungime " << L << " este: " << dp [L] << endl ;
return 0 ;
}