Dana jest tablica liczb, np. A=[1,5,3,5,4,12,8,1,2,6] i liczba T, np. T=17. Trzeba znaleźć podzbiór zbioru A, który się sumuje do T. Znalazłem pseudokod, ale nie mogę zrozumieć, jak odczytać wynik, czyli ten szukany podzbiór. Oczywiście to wszystko jest oparte o programowanie dynamiczne. Będę wdzięczny za pomoc.
Pseudokod:
SUBSET-SUM(A,n,T)
niech F[T+1][n+1] będzie nową tablicą boolowską
for i:=0 to n
F[0][i] = TRUE
for i:=0 to T
F[i][0] = FALSE
for i:=1 to T
for j:=1 to n
F[i][j] = F[i][j-1]
if i >= A[j-1]
F[i][j] = F[i][j] || F[i - A[j-1]][j-1]
Przepisane do C++:
#include <iostream>
using namespace std;
const int N = 10;
const int T = 17;
bool F[T+1][N+1];
int A[10] = {1,5,3,5,4,12,8,1,2,6};
int main(){
for (int i=0; i<=N; i++)
F[0][i]=true;
for (int i=0; i<=T; i++)
F[i][0]=false;
for (int i=1; i<=T; i++)
for (int j=1; j<=N; j++) {
F[i][j]=F[i][j-1];
if (i >= A[j-1])
F[i][j]=(F[i][j] || F[i - A[j-1]][j-1]);
}
for (int i=0; i<=T; i++){
for (int j=0; j<=N; j++)
cout << F[i][j] << " ";
cout << endl;
}
}