正数数组的最小不可组成和

正数数组的最小不可组成和

题目描述

给定一个正数数组arr，其中所有的值都为整数，以下是最小不可组成和的概念

• 把arr每个子集内的所有元素加起来会出现很多值，其中最小的记为min，最大的记为max
• 在区间[min, max]上，如果有数不可以被arr某一个子集相加得到，那么其中最小的那个数是arr的最小不可组成和
• 在区间[min, max]上，如果所有的数都可以被arr的某一个子集相加得到，那么max+1是arr的最小不可组成和

请写函数返回正数数组arr的最小不可组成和

时间复杂度为 O ( n × ∑ i = 1 n a r r i ) O(n \times \sum_{i=1}^n arr_i) O(n×∑i=1n​arri​)，额外空间复杂度为 O ( ∑ i = 1 n a r r i ) O(\sum_{i=1}^n arr_i) O(∑i=1n​arri​)

输入描述：

第一行一个整数N，表示数组长度。
接下来一行N个整数表示数组内的元素。

输出描述：

输出一个整数表示数组的最小不可组成和

示例1

输入

3
2 3 9

输出

4

示例2

输入

3
1 2 4

输出

8

说明

3 = 1 + 2
5 = 1 + 4
6 = 2 + 4
7 = 1 + 2 + 4

备注：

1 ⩽ N ⩽ 100 1 \leqslant N \leqslant 100 1⩽N⩽100
N < ( ∑ i = 1 N a r r i ) ⩽ 1 0 4 N < (\sum_{i=1}^N arr_i) \leqslant 10^4 N<(∑i=1N​arri​)⩽104

---

题解：

动态规划，设 f[j] 表示 j 能否被 arr 的子集相加得到，如果 arr[0…i] 上的子集累加和可以得到 k ，那么 arr[0…i+1] 上的子集必然可以累加出 k+arr[i+1]，后面的就是类似背包问题转移方程，具体见代码。

代码：

#include <cstdio>

using namespace std;

const int N = 100;
const int M = 10001;

bool f[M];
int a[N];

int main(void) {
    int n, val;
    scanf("%d", &n);
    int mn = M, sum = 0;
    for ( int i = 0; i < n; ++i ) {
        scanf("%d", a + i);
        if ( a[i] < mn ) mn = a[i];
        sum += a[i];
    }
    f[0] = true;
    for ( int i = 0; i < n; ++i ) {
        for ( int j = sum; j >= a[i]; --j ) {
            f[j] |= f[j - a[i]];
        }
    }
    int ret = sum + 1;
    for ( int i = mn; i <= sum; ++i ) {
        if ( !f[i] ) {
            ret = i;
            break;
        }
    }
    return 0 * printf("%d\n", ret);
}