华为机试C语言-篮球比赛_题目描述 篮球赛即将打响,cmonkey负责组织篮球赛的对抗安排。现在一共有n支队伍,

题目描述：https://pycoder.blog.csdn.net/article/details/125270003?spm=1001.2014.3001.5502

动态规划 ： dp[i] 表示是否能组成容量为 i 的战斗力。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>


int main(void) {
    int arr[10] = {0};
    int sum = 0;
    int target;
    bool dp[50000] = {0};
    int max = 0;

    for (int i = 0; i < 10; i++) {
        scanf("%d", &arr[i]);
        sum += arr[i];
    }

    target = sum / 2;

    dp[0] = true;
    for (int i = 0; i < 10; i++) {
        for (int j = target; j > 0; j--) {  // 如果是从小到大的话，会存在重复计算球员战斗力的情况
            int pre = j - arr[i];
            if (pre >= 0) {
                dp[j] = dp[j] || dp[pre];
            }

            if (dp[j]) {
                max = fmax(max, j);
            }
        }
    }

    printf("%d\n", abs((sum - max) - max));

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39