代码来自:https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
应重点记忆上面链接中第二种动态规划的方法,因为第一种方法是指数复杂度。这里只记录动态规划的算法。
/*
We can solve the problem in Pseudo-polynomial time using Dynamic programming.
We create a boolean 2D table subset[][] and fill it in bottom up manner.
The value of subset[i][j] will be true if there is a subset of set[0..j-1] with sum equal to i.,
otherwise false. Finally, we return subset[sum][n]
*/
// Returns true if there is a subset of
// set[] with sun equal to given sum
static boolean 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
boolean subset[][] =
new boolean[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++)
System.out.println (subset[i][j]);
} */
return subset[sum][n];
}