Динамическое программирование обеспечивает очень элегантный способ решения проблемы суммы подмножеств. Задача о сумме подмножества: определить, существует ли подмножество с суммой = k.
Но я не могу понять, как мы можем вывести все подмножества с sum = k. Любые указатели на то, как изменить следующую функцию на основе динамического программирования, которая просто проверяет и возвращает истину, если существует требуемое подмножество. Пожалуйста, обратитесь ЗДЕСЬ для получения дополнительных сведений.
// Returns true if there is a subset of set[] with sun equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
// The value of subset[i][j] will be true if there is a subset of set[0..j-1]
// with sum equal to i
bool subset[sum+1][n+1];
// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
subset[0][i] = true;
// If sum is not 0 and set is empty, then answer is false
for (int i = 1; i <= sum; i++)
subset[i][0] = false;
// Fill the subset table in botton up manner
for (int i = 1; i <= sum; i++)
{
for (int j = 1; j <= n; j++)
{
subset[i][j] = subset[i][j-1];
if (i >= set[j-1])
subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1];
}
}
/* // uncomment this code to print table
for (int i = 0; i <= sum; i++)
{
for (int j = 0; j <= n; j++)
printf ("%4d", subset[i][j]);
printf("\n");
} */
return subset[sum][n];
}