华为OD机试 - MELON的难题 - 动态规划（Java 2023 B卷 100分）_华为机考melon的难题

作者：酷酷是懒虫 | 2024-07-15 00:42:39

踩

华为机考melon的难题

在这里插入图片描述

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

第1行输入为雨花石个数: n，0<n<31。
第2行输入为空格分割的各雨化石重量: m[0] m[1] … m[n- 1]， 0< m[k] < 1001
不需要考虑异常输入的情况。

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

看到题目，我的第一反应是采用动态规划求解，目标值是雨花石重量总和的一半，从当前雨花石中最少拿出几块，满足两人的雨花石均分。

先区分一下动态规划与分治方法，都是将原问题拆分成若干个子问题，分别求解，再组合子问题的结果选出最优解

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/827099