问题描述

给定一组雨花石的重量，要求将这些石头分成两组，使得两组的重量相等。如果可以实现这样的分组， 输出所需的最小石头数量；如果无法均分，则输出 $-1$。

解题思路

1. 计算总重量

首先计算所有雨花石的总重量 sum_m。

2. 奇偶性检查

如果 sum_m 为奇数，则无法均分，直接输出 -1。

3. 背包动态规划

设定目标重量为 sum_m / 2。使用动态规划数组 dp，其中 dp[j] 表示形成重量 j 所需的最小石头数量。

• 初始化 dp[0] 为 0（不需要任何石头形成 0 重量），其余初始化为一个较大的数（如 99，因为 n 最大只有 30）。
• 遍历每个雨花石的重量，并更新 dp 数组，以找出形成每个可能重量所需的最少石头数量。

4. 结果输出

最后检查 dp[sum_m / 2]。

• 如果它仍然是初始值，说明无法组成该重量，输出 -1。
• 否则，输出所需的最小石头数量。

5. 时间复杂度

该算法的时间复杂度为 O(n * sum_m / 2)，其中 n 是石头的数量，sum_m 是所有石头的总重量。

问题本质分析

本问题实质上是一个变形的“0-1背包问题”。我们需要通过选取雨花石的重量来形成一个特定的目标重量， 这与背包问题中通过物品重量来填充背包的思路类似。通过动态规划的方式，我们可以高效地计算出是否能够达到目标重量， 并在此过程中记录形成该重量所需的最小石头数量。

cpp

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int numStones;  // 用于存储雨花石的数量
    cin >> numStones;  

    vector<int> stoneWeights(numStones);  // 存储每个雨花石的重量
    int totalWeight = 0;  // 用于存储所有雨花石的总重量

    // 输入每个雨花石的重量，并计算总重量
    for (int i = 0; i < numStones; i++) {
        cin >> stoneWeights[i];  
        totalWeight += stoneWeights[i];  // 累加当前雨花石重量到总重量
    }

    // 如果总重量是奇数，则无法均分
    if (totalWeight % 2 != 0) {  
        cout << -1 << endl;  
        return;  
    }

    // 计算每个人应该得到的目标重量
    int targetWeight = totalWeight / 2;  
    vector<int> minStonesRequired(targetWeight + 1, 99);  // DP数组，初始化为99（较大的数）
    minStonesRequired[0] = 0;  // 表示形成重量0需要0块石头

    // 动态规划计算，找出形成目标重量targetWeight所需的最少石头数量
    for (int i = 0; i < numStones; i++) {  // 遍历每个雨花石
        for (int j = targetWeight; j >= stoneWeights[i]; j--) {  // 从targetWeight向下遍历
            if (j == stoneWeights[i])  // 如果当前重量等于雨花石的重量
                minStonesRequired[j] = min(minStonesRequired[j], 1);  // 直接赋值为1
            else  
                minStonesRequired[j] = min(minStonesRequired[j], minStonesRequired[j - stoneWeights[i]] + 1);  // 更新dp[j]
        }
    }

    // 检查是否能形成目标重量targetWeight
    if (minStonesRequired[targetWeight] == 99)  // 如果无法形成该重量
        cout << -1 << endl;  
    else  
        cout << minStonesRequired[targetWeight] << endl;  // 输出所需的最小石头数量
}

int main() {
    solve();
    return 0;
}

python

def solve():
    num_stones = int(input())  # 输入雨花石的数量
    stone_weights = list(map(int, input().split()))  # 输入每个雨花石的重量
    total_weight = sum(stone_weights)  # 计算所有雨花石的总重量

    # 如果总重量是奇数，则无法均分
    if total_weight % 2 != 0:
        print(-1)
        return

    # 计算每个人应该得到的目标重量
    target_weight = total_weight // 2
    min_stones_required = [99] * (target_weight + 1)  # DP数组，初始化为99
    min_stones_required[0] = 0  # 表示形成重量0需要0块石头

    # 动态规划计算，找出形成目标重量target_weight所需的最少石头数量
    for weight in stone_weights:  # 遍历每个雨花石
        for j in range(target_weight, weight - 1, -1):  # 从target_weight向下遍历
            min_stones_required[j] = min(min_stones_required[j], min_stones_required[j - weight] + 1)

    # 检查是否能形成目标重量target_weight
    if min_stones_required[target_weight] == 99:  # 如果无法形成该重量
        print(-1)
    else:
        print(min_stones_required[target_weight])  # 输出所需的最小石头数量
# 主函数
if __name__ == "__main__":
    solve()

java

import java.util.Scanner;

public class Main {
    public static void solve() {
        Scanner scanner = new Scanner(System.in);
        
        int numStones = scanner.nextInt();  // 输入雨花石的数量
        int[] stoneWeights = new int[numStones];  // 存储每个雨花石的重量
        int totalWeight = 0;  // 用于存储所有雨花石的总重量

        // 输入每个雨花石的重量，并计算总重量
        for (int i = 0; i < numStones; i++) {
            stoneWeights[i] = scanner.nextInt();
            totalWeight += stoneWeights[i];
        }

        // 如果总重量是奇数，则无法均分
        if (totalWeight % 2 != 0) {  
            System.out.println(-1);
            scanner.close();
            return;  
        }

        // 计算每个人应该得到的目标重量
        int targetWeight = totalWeight / 2;
        int[] minStonesRequired = new int[targetWeight + 1];  // DP数组
        for (int i = 0; i <= targetWeight; i++) {
            minStonesRequired[i] = 99;  // 初始化为99
        }
        minStonesRequired[0] = 0;  // 表示形成重量0需要0块石头

        // 动态规划计算，找出形成目标重量targetWeight所需的最少石头数量
        for (int weight : stoneWeights) {  // 遍历每个雨花石
            for (int j = targetWeight; j >= weight; j--) {  // 从targetWeight向下遍历
                minStonesRequired[j] = Math.min(minStonesRequired[j], minStonesRequired[j - weight] + 1);
            }
        }

        // 检查是否能形成目标重量targetWeight
        if (minStonesRequired[targetWeight] == 99)  // 如果无法形成该重量
            System.out.println(-1);
        else  
            System.out.println(minStonesRequired[targetWeight]);  // 输出所需的最小石头数量

        scanner.close();
    }

    public static void main(String[] args) {
        solve();
    }
}

题目内容

MELON有一堆精美的雨花石（数量为 $n$，重量各异），准备送给 S 和 W 。

MELON希望送给俩人的雨花石重量一致，请你设计一个程序，帮MELON确认是否能将雨花石平均分配。

输入描述

第 $1$ 行输入为雨花石个数：$n$ ， $0 < n < 31$ 。

第 $2$ 行输入为空格分割的各雨花石重量：$m[0] m[1] ….. m[n - 1]$， $0 < m[k] < 1001$。

不需要考虑异常输入的情况。

输出描述

如果可以均分，从当前雨花石中最少拿出几块，可以使两堆的重量相等；

如果不能均分，则输出 $-1$ 。

样例1

输入

4
1 1 2 2

输出

2

说明

输入第一行代表共 $4$ 颗雨花石，

第二行代表 $4$ 颗雨花石重量分别为 $1$、$1$、$2$ 、$2$ 。

均分时只能分别为 $1,2$，需要拿出重量为 $1$ 和 $2$ 的两块雨花石，所以输出 $2$

样例2

输入

10
1 1 1 1 1 9 8 3 7 10

输出

3

说明

输入第一行代表共 $10$ 颗雨花石，

第二行代表 $4$ 颗雨花石重量分别为$1、1、1、1、1、9、8、3、7、10$ 。

均分时可以 $1,1,1,1,1,9,7$ 和 $10,8,3$ ，也可以 $1,1,1,1,9,8$ 和 $10,7,3,1$ ，或者其他均分方式，但第一种只需要拿出重量为 $10,8,3$ 的 $3$ 块雨花石，第二种需要拿出 $4$ 块，所以输出 $3$ (块数最少)。