动力装置可以缩小并变成背包吗？

Question

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

以下是硬币变化的代码片段，其中一个具有 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 ⁿ个子集，仅打印它们将花费指数时间。
像子集总和、背包或硬币找零这样的问题与幂集有关，因为你隐式地必须生成所有子集，但它们和幂集之间有很大的区别。在这些问题中，您仅计算一些子集，并且不需要显式生成这些子集。例如，如果问题要求您找到将 X 美元兑换为某些硬币的所有方法，那么您无法在线性时间内解决这个问题，因为您必须生成所有所需的子集，并且可能有 2 ⁿ个。