powerset能不能缩减改成背包?
Can powerset be reduced and transformed to knapsack?
请问powerset问题能否转化为背包问题?在我看来,它们是相同的,例如我们可以将其视为 powerset 的更改问题我启动 2 个递归调用的每个递归阶段(一个采用第 i
个元素,另一个绕过它).我也可以像背包问题一样用动态规划来解决它,所以这让我想知道是否所有的幂集问题都可以转化为背包问题。那是对的吗 ?
以下是硬币变化的代码片段,一个是O(2N)时间复杂度,一个是动态规划O(N2) 运行时。
// O(2^N) time complexity
void bruteforce(int[] coins, int i, int N, String expr)
{
if (i == coins.length) {
if (N == 0)
count++;
return;
}
if (N >= coins[i])
recursion(coins, i, N - coins[i], expr + " " + coins[i]);
recursion(coins, i + 1, N, expr);
}
// O(N^2) time complexity
int dynamicProgramming(int[] coins, int N)
{
int [] dp = new int[N + 1];
dp[0] = 1;
for(int i = 0; i < coins.length; i++)
for(int j = coins[i]; j <= N; j++)
dp[j] += dp[j - coins[i]];
return dp[N];
}
求幂集(生成集合的所有子集)不能以复杂度优于 O(2n) 的方式完成,因为有 2n 个子集,仅打印它们将花费指数时间。
子集求和、背包或硬币变化等问题都与 powerset 有关,因为你 implicity 必须生成所有子集,但它们与 powerset 之间存在很大差异。在这些问题中,您只计算一些子集,并且不需要 explicity 生成这些子集。例如,如果问题要求您找到将 X 美元兑换成一些硬币的所有方法,那么您无法在线性时间内解决这个问题,因为您必须生成所有需要的子集,并且可能有 2n 个。
请问powerset问题能否转化为背包问题?在我看来,它们是相同的,例如我们可以将其视为 powerset 的更改问题我启动 2 个递归调用的每个递归阶段(一个采用第 i
个元素,另一个绕过它).我也可以像背包问题一样用动态规划来解决它,所以这让我想知道是否所有的幂集问题都可以转化为背包问题。那是对的吗 ?
以下是硬币变化的代码片段,一个是O(2N)时间复杂度,一个是动态规划O(N2) 运行时。
// O(2^N) time complexity
void bruteforce(int[] coins, int i, int N, String expr)
{
if (i == coins.length) {
if (N == 0)
count++;
return;
}
if (N >= coins[i])
recursion(coins, i, N - coins[i], expr + " " + coins[i]);
recursion(coins, i + 1, N, expr);
}
// O(N^2) time complexity
int dynamicProgramming(int[] coins, int N)
{
int [] dp = new int[N + 1];
dp[0] = 1;
for(int i = 0; i < coins.length; i++)
for(int j = coins[i]; j <= N; j++)
dp[j] += dp[j - coins[i]];
return dp[N];
}
求幂集(生成集合的所有子集)不能以复杂度优于 O(2n) 的方式完成,因为有 2n 个子集,仅打印它们将花费指数时间。
子集求和、背包或硬币变化等问题都与 powerset 有关,因为你 implicity 必须生成所有子集,但它们与 powerset 之间存在很大差异。在这些问题中,您只计算一些子集,并且不需要 explicity 生成这些子集。例如,如果问题要求您找到将 X 美元兑换成一些硬币的所有方法,那么您无法在线性时间内解决这个问题,因为您必须生成所有需要的子集,并且可能有 2n 个。