子集枚举

子集枚举是一种常见的枚举算法，用于列举一个集合的所有子集。其基本思路是对于每个元素，可以选择将其加入子集中或不加入子集中，通过枚举所有可能的选择来得到所有的子集。

以下是一个简单的示例代码，用于列举一个集合的所有子集：

def subsets(nums):
    res = [[]]
    for num in nums:
        res += [item + [num] for item in res]
    return res

其中，nums是输入的集合，res是保存所有子集的列表。该算法的时间复杂度为O(2^n)，其中n为集合的大小。

相关问题

有 n 张卡片，正反面皆有数字，有正有负。今要求每张卡片都从正反面中选一个数字，令他们的积最大。 除了子集枚举（DFS），还可以怎么做？（复杂度最高 O(n log n)）

可以考虑贪心算法。先将所有卡片的正面数字从小到大排序，将所有负数记录下来。然后从第一张卡片开始，如果正面数字为正数，则选取正面数字，否则选取反面数字。对于负数，如果当前选取的卡片为负数，则选取反面数字，否则选取正面数字。这样就能保证积最大。
复杂度O(nlogn)

编写以一个C/C++语言程序0/1背包枚举法 问题：给定n个重量为{w1,w2,···,wn}、价值为{v1,v2,···,vn}的物品和一个容量为C的背包，0/1背包是一个求解这些物品中的一个最有价值的子集，并且能够装入到背包中。

在C/C++中，使用0/1背包问题的枚举法通常涉及到动态规划的思想。这里简单概述一下基本步骤：

1. 定义状态：创建一个二维数组dp[i][j]，其中i表示物品的数量范围(0...n)，j表示当前背包剩余容量范围(0...C)。dp[i][j]表示前i个物品能够达到的最大总价值，当背包容量为j时。

2. 初始化：对于每个物品i，dp[i][0]设置为0，因为如果背包容量为0，无法放入任何物品。

3. 枚举决策：对于每一个物品i，有两种选择：
- 不选：将dp[i][j]的值保持不变，即dp[i][j] = dp[i-1][j]
- 选：如果物品i的重量小于等于背包容量j，则更新dp[i][j]为dp[i-1][j-w_i] + v_i（表示选上第i个物品），否则dp[i][j]不变。

4. 更新结果：遍历结束后，dp[n][C]就是整个背包问题的最大价值。

5. 输出解决方案：为了找到最优解，可以回溯整个dp数组，找出哪些物品被选择了。

下面是一个简单的C++示例：

#include <iostream>
using namespace std;

int knapSack(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1];
    
    // 枚举填充过程
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                dp[i][w] = 0;
            else if (wt[i-1] <= w)
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
            else
                dp[i][w] = dp[i-1][w];
        }
    }

    return dp[n][W];
}

int main() {
    int W = 50, wt[] = {10, 20, 30}, val[] = {60, 100, 120}, n = sizeof(wt)/sizeof(wt[0]);
    cout << "最大价值: " << knapSack(W, wt, val, n);
    return 0;
}