E卷-刷题笔记合集🔗

(200分)105.MELON的难题

MELON的难题

问题描述

MELON 有一堆精美的雨花石，想要将它们平均分配给 S 和 W 两个人。每块雨花石的重量各不相同，MELON 希望两人得到的雨花石总重量相等。请你设计一个程序，帮助 MELON 确认是否能够实现平均分配，如果可以，还需要计算出最少需要拿出多少块雨花石才能实现平均分配。

输入格式

输入包含两行：

第一行为一个整数 ，表示雨花石的总数量，。

第二行包含 个用空格分隔的整数 ，表示每块雨花石的重量，。

输出格式

如果能够平均分配，输出一个整数，表示最少需要拿出的雨花石数量，使得剩下的雨花石可以平均分配给两个人。

如果无法平均分配，则输出 。

样例输入1

4
1 1 2 2

样例输出1

2

样例输入2

10
1 1 1 1 1 9 8 3 7 10

样例输出2

3

样例解释

数据范围

题解

动态规划

这道题目本质上是一个变形的 0-1 背包问题。我们的目标是找到一种方法，将雨花石分成两组，使得两组的重量相等。解题思路如下：

1. 首先计算所有雨花石的总重量 。如果 是奇数，则无法平均分配，直接返回 。

2. 如果 是偶数，我们的目标就是找到一组雨花石，使其重量和恰好为 。

3. 使用动态规划解决这个问题。创建一个一维数组 ，其中 表示装满重量为 的背包所需的最少物品数。

4. 初始化 数组：，其他位置初始化为一个不可能的大值（如 ）。

5. 对于每个雨花石，更新 数组。状态转移方程为：

   (当 时)

6. 最后，如果 () 等于 ，说明无法平分，返回 。否则，返回 。

这个解法的时间复杂度是 ，空间复杂度是 。

参考代码

• Python

# 输入获取
n = int(input())
nums = list(map(int, input().split()))

# 算法入口
def solve():
    # 所有雨花石重量之和
    sumV = sum(nums)

    # 如果重量之和不能整除2，则必然无法平分
    if sumV % 2 != 0:
        return -1

    # 背包承重
    bag = sumV // 2

    # 一维dp数组
    dp = [n + 1] * (bag + 1)
    dp[0] = 0

    for num in nums:
        for j in range(bag, num - 1, -1):
            dp[j] = min(dp[j], dp[j - num] + 1)

    # 如果装满背包的最少物品数为n+1, 则说明没有平分方案
    if dp[bag] == n + 1:
        return -1
    else:
        return min(n - dp[bag], dp[bag])

# 算法调用
print(solve())

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

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int solve(int n, int* nums) {
    // 所有雨花石重量之和
    int sumV = 0;
    for (int i = 0; i < n; i++) {
        sumV += nums[i];
    }

    // 如果重量之和不能整除2，则必然无法平分
    if (sumV % 2 != 0) {
        return -1;
    }

    // 背包承重
    int bag = sumV / 2;

    // 一维dp数组
    int* dp = (int*)malloc((bag + 1) * sizeof(int));
    for (int i = 0; i <= bag; i++) {
        dp[i] = n + 1;
    }
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = bag; j >= nums[i]; j--) {
            dp[j] = MIN(dp[j], dp[j - nums[i]] + 1);
        }
    }

    // 如果装满背包的最少物品数为n+1, 则说明没有平分方案
    int result;
    if (dp[bag] == n + 1) {
        result = -1;
    } else {