体积（题解）

体积（深度优先搜索）

题目描述

给出 n n n 件物品，每件物品有一个体积 v i v_i vi​ ，求从中取出若干件物品能够组成的不同的体积和有多少种可能。

---

输入格式

第 1 1 1 行 1 1 1 个正整数，表示 n n n 。
第 2 2 2 行 n n n 个正整数，表示 v i v_i vi​ ，每两个数之间用一个空格隔开。

---

输出格式

一行一个数，表示不同的体积和有多少种可能。

---

样例

样例输入

3
1 3 4

样例输出

6

数据范围与提示

对于 30 % 30\% 30% 的数据满足： n ≤ 5 n ≤ 5 n≤5 ， v i ≤ 10 v_i ≤ 10 vi​≤10 。
对于 60 % 60\% 60% 的数据满足： n ≤ 10 n ≤ 10 n≤10 ， v i ≤ 20 v_i ≤ 20 vi​≤20 。
对于 100 % 100\% 100% 的数据满足： n ≤ 20 n ≤ 20 n≤20 ， 1 ≤ v i ≤ 50 1 ≤ v_i ≤ 50 1≤vi​≤50 。

---

题解

第一眼见到这题目时，以为就是一个暴力搜索
于是，我就写下了这样的代码

#include <cstdio>
bool b[1005];
int n, a[35];
bool flag[35];
void dfs(int t, int sum) {
    if (t > n)
        return;
    b[sum] = true;
    for (int i = 1; i <= n; i++) {
        if (!flag[i]) {
            flag[i] = true;
            dfs(t + 1, sum + a[i]);
            flag[i] = false;
        }
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    dfs(1, 0);
    int sum = 0;
    for (int i = 0; i <= 1000; i++) {
        if (b[i])
            sum++;
    }
    printf("%d", sum);
    return 0;
}

然后就 Time Limit Exceeded 60 60 60 分
于是，我又做出这样的修改将第 9 9 9 行的

i = 1;

改为

i = t;

然后兴奋的去提交，结果。。。Time Limit Exceeded 80 80 80 分 （多水了 20 20 20 分， 我好开心）
测试了一下，发现 n = 15 n = 15 n=15 就炸了

---

正确思路：
1. 1. 1. 先定义一个 b o o l bool bool 类型的桶，来保存当前发现的体积有没有被发现过，桶的大小为 m a x n × m a x v = 20 × 50 = 1000 max_n × max_v = 20 × 50 = 1000 maxn​×maxv​=20×50=1000 ,为了防止溢出，我们就定义 1005 1005 1005 好了。

2. 2. 2. 在深搜函数里面传入两个参量 t t t 和 s u m sum sum , t t t 表示目前遍历到体积的下标， s u m sum sum 表示已有的体积和。

3. 3. 3. 递归有两种情况，第一种是选择这一个体积，第二种是不选择，直接跳过

4. 4. 4. 边界条件： 如果 t > n t > n t>n 表示已经遍历完了，将当前的 s u m sum sum 置位 t r u e true true ，结束递归

5. 5. 5. 在主函数内遍历这个 b o o l bool bool 类型的数组，如果为 t r u e true true , a n s ans ans 就加一

---

完整 c o d e code code

#include <cstdio>
bool b[1005];
int n, a[35];
void dfs(int t, int sum) {
    if (t > n) {
        b[sum] = true;
        return;
    }
    dfs(t + 1, sum + a[t]);
    dfs(t + 1, sum);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    dfs(1, 0);
    int sum = 0;
    for (int i = 1; i <= 1000; i++) {
        if (b[i])
            ans++;
    }
    printf("%d", ans);
    return 0;
}