返回目录

题目描述：MELON的难题（本题200分）

MELON有一堆精美的雨花石（数量为n，重量各异），准备送给S和W。MELON希望送给俩人的雨花石重量一致，请你设计一个程序，帮MELON确认是否能将雨花石平均分配。

输入描述

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

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

输出描述

如果可以均分，从当前雨花石中最少拿出几块，可以使两堆的重量相等:如果不能均分，则输出-1。

示例：

01背包问题的思路：

题目要求将雨花石平均分配，即找到一种方法，使得从雨花石中拿出最少的数量，使得两堆雨花石的重量相等。这个问题可以转化为一个01背包问题：从给定的雨花石中选取一些，使得它们的重量之和等于总重量的一半，且选取的雨花石数量最少。

01背包问题的核心思路是使用动态规划。具体步骤如下：

计算所有雨花石的总重量。如果总重量为奇数，那么无法将雨花石平均分配，直接输出-1。

如果总重量为偶数，我们的目标是找到一些雨花石，使得它们的重量之和等于总重量的一半。定义一个动态规划数组dp，其中dp[j]表示从雨花石中选取一些，使得它们的重量之和为j时，所需的最少雨花石数量。

初始化dp数组，将除了dp之外的其他元素设置为n，表示最坏情况下需要拿出所有雨花石。

遍历每一块雨花石，对于每一块雨花石，从targetWeight开始递减，更新dp数组。如果使用当前雨花石能够减少所需雨花石数量，则更新dp[j]。

最后，检查dp[targetWeight]的值。如果它等于n，表示无法找到满足条件的雨花石组合，输出-1。否则，输出dp[targetWeight]，表示从当前雨花石中最少拿出几块，可以使两堆的重量相等。

Python算法源码

def main():
    n = int(input())  # 输入雨花石个数
    stones = list(map(int, input().split()))  # 输入雨花石重量

    total_weight = sum(stones)  # 计算雨花石总重量

    if total_weight % 2 != 0:  # 如果总重量为奇数，无法均分
        print(-1)
    else:
        target_weight = total_weight // 2  # 目标重量为总重量的一半

        # 创建动态规划数组，dp[i]表示前i块雨花石中是否能够取出一些雨花石使得重量和为j
        dp = [0] * (target_weight + 1)

        # 初始化dp数组，将除了dp[0]之外的所有值设为n，表示最大需要拿出n块雨花石
        for i in range(1, target_weight + 1):
            dp[i] = n

        # 遍历每一块雨花石
        for stone in stones:
            # 更新dp数组，从后往前更新，避免重复使用同一块雨花石
            for j in range(target_weight, stone - 1, -1):
                # 如果当前重量可以由前面的雨花石组成，更新dp[j]为最小需要拿出的雨花石数量
                dp[j] = min(dp[j], dp[j - stone] + 1)

        # 如果dp[target_weight]仍然等于n，表示无法均分雨花石
        if dp[target_weight] == n:
            print(-1)
        else:
            # 输出最少需要拿出的雨花石数量
            print(dp[target_weight])

if __name__ == "__main__":
    main()

C算法源码

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

int min(int a, int b) {
    return (a < b) ? a : b;
}

int main() {
    int n;
    scanf("%d", &n);  // 输入雨花石个数

    int* stones = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &stones[i]);  // 输入雨花石重量
    }

    int totalWeight = 0;
    for (int i = 0; i < n; i++) {
        totalWeight += stones[i];  // 计算雨花石总重量
    }

    if (totalWeight % 2 != 0) {  // 如果总重量为奇数，无法均分
        printf("-1\n");
    } else {
        int targetWeight = totalWeight / 2;  // 目标重量为总重量的一半

        // 创建动态规划数组，dp[i]表示是否能够取出一些雨花石使得重量和为i
        int* dp = (int*)malloc((targetWeight + 1) * sizeof(int));
        dp[0] = 0; // 初始化dp[0]为0，其余为n表示最大需要拿出n块雨花石
        for (int i = 1; i <= targetWeight; i++) {
            dp[i] = n;
        }

        // 遍历每一块雨花石
        for (int i = 0; i < n; i++) {
            int weight = stones[i];
            // 更新dp数组，从后往前更新，避免重复使用同一块雨花石
            for (int j = targetWeight; j >= weight; j--) {
                // 如果当前重量可以由前面的雨花石组成，更新dp[j]为最小需要拿出的雨花石数量
                dp[j] = min(dp[j], dp[j - weight] + 1);
            }
        }

        // 如果dp[targetWeight]等于n，表示无法均分雨花石
        if (dp[targetWeight] == n) {
            printf("-1\n");
        } else {
            // 输出最少需要拿出的雨花石数量
            printf("%d\n", dp[targetWeight]);
        }

        free(stones);
        free(dp);
    }

    return 0;
}

Java算法源码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 输入雨花石个数
        int[] stones = new int[n];
        for (int i = 0; i < n; i++) {
            stones[i] = scanner.nextInt();  // 输入雨花石重量
        }

        int totalWeight = 0;
        for (int stone : stones) {
            totalWeight += stone;  // 计算雨花石总重量
        }

        if (totalWeight % 2 != 0) {  // 如果总重量为奇数，无法均分
            System.out.println(-1);
        } else {
            int targetWeight = totalWeight / 2;  // 目标重量为总重量的一半

            // 创建动态规划数组，dp[i]表示前i块雨花石中是否能够取出一些雨花石使得重量和为j
            int[] dp = new int[targetWeight + 1];
            dp[0] = 0;

            // 初始化dp数组，将除了dp[0]之外的所有值设为n，表示最大需要拿出n块雨花石
            for (int i = 1; i <= targetWeight; i++) {
                dp[i] = n;
            }

            // 遍历每一块雨花石
            for (int i = 1; i <= n; i++) {
                int weight = stones[i - 1];
                // 更新dp数组，从后往前更新，避免重复使用同一块雨花石
                for (int j = targetWeight; j >= weight; j--) {
                    // 如果当前重量可以由前面的雨花石组成，更新dp[j]为最小需要拿出的雨花石数量
                    dp[j] = Math.min(dp[j], dp[j - weight] + 1);
                }
            }

            // 如果dp[targetWeight]仍然等于n，表示无法均分雨花石
            if (dp[targetWeight] == n) {
                System.out.println(-1);
            } else {
                // 输出最少需要拿出的雨花石数量
                System.out.println(dp[targetWeight]);
            }
        }
    }
}