刷题笔记合集🔗

题目描述

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 ≤ n ≤ 30
• 1 ≤ m[k] ≤ 1000

样例输入1

4
1 1 2 2

样例输出1

2

样例说明1

输入第一行代表共4颗雨花石，第二行代表4颗雨花石重量分别为1、1、2、2。 均分时只能分别为1,2，需要拿出重量为1和2的两块雨花石，所以输出2。

样例输入2

10
1 1 1 1 1 9 8 3 7 10

样例输出2

3

样例说明2

输入第一行代表共10颗雨花石，第二行代表雨花石重量。 均分方案有多种:

1. 1,1,1,1,1,9,7和10,8,3 (拿出3块)
2. 1,1,1,1,9,8和10,7,3,1 (拿出4块)
3. ...其他均分方式 第一种方案只需要拿出重量为10,8,3的3块雨花石，是最少的，所以输出3。

题目解析

本题是一个变种的01背包问题。关键点:

1. 问题分析

   • 首先判断总重量是否能被2整除
   • 如果可以整除，则尝试找到最少数量的石头组成一半重量
   • 如果找不到这样的组合，说明无法平分

2. 动态规划实现

   • dp[i][j]表示从前i个石头中选择，能装满重量j的最少石头数
   • 状态转移:dp[i][j] = min(dp[i-1][j], dp[i-1][j-w] + 1)
   • 初始化:dp[0][0]=0, dp[0][j]=n(j>0)

3. 求解步骤

   • 计算总重量sum
   • 如果sum为奇数，返回-1
   • 否则目标重量为sum/2
   • 使用dp求解最少需要的石头数

时间复杂度: O(n*sum)，其中n是石头数量，sum是总重量

参考代码

def solve():
    # 读取输入
    n = int(input())
    stones = list(map(int, input().split()))
    
    # 计算总重量
    total = sum(stones)
    if total % 2 != 0:
        return -1
        
    target = total // 2
    
    # dp[i][j]表示从前i个石头中选择，能装满重量j的最少石头数
    dp = [[n+1] * (target + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    
    # 动态规划
    for i in range(1, n + 1):
        w = stones[i-1]
        for j in range(target + 1):
            if j < w:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-w] + 1)
    
    # 如果无法达到目标重量
    if dp[n][target] == n+1:
        return -1
        
    return dp[n][target]

if __name__ == "__main__":
    print(solve())

#include