powerset能不能缩减改成背包？

Question

请问powerset问题能否转化为背包问题？在我看来，它们是相同的，例如我们可以将其视为 powerset 的更改问题我启动 2 个递归调用的每个递归阶段（一个采用第 i 个元素，另一个绕过它).我也可以像背包问题一样用动态规划来解决它，所以这让我想知道是否所有的幂集问题都可以转化为背包问题。那是对的吗？

以下是硬币变化的代码片段，一个是O(2^N)时间复杂度，一个是动态规划O(N²) 运行时。

// 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];
}

Answer 1

求幂集（生成集合的所有子集）不能以复杂度优于 O(2ⁿ) 的方式完成，因为有 2ⁿ 个子集，仅打印它们将花费指数时间。
子集求和、背包或硬币变化等问题都与 powerset 有关，因为你 implicity 必须生成所有子集，但它们与 powerset 之间存在很大差异。在这些问题中，您只计算一些子集，并且不需要 explicity 生成这些子集。例如，如果问题要求您找到将 X 美元兑换成一些硬币的所有方法，那么您无法在线性时间内解决这个问题，因为您必须生成所有需要的子集，并且可能有 2ⁿ 个。

powerset能不能缩减改成背包？

Can powerset be reduced and transformed to knapsack?

algorithm

recursion

knapsack-problem

dynamic-programming

powerset