一道ACM题,我新手,完全没思路

一道ACM题,我新手,完全没思路
Description
给出N个整数,每个数范围在[-1000,1000],问能不能在N个数中选出一些数（但不可以不选,且每个数最多只能被选择一次）,使他们的和为0
Input
Q
czmm815 1年前 已收到1个回答 举报
赞

潇洒forever 幼苗

共回答了23个问题采纳率：82.6% 举报

你新手?那你可以去看看动态规划的背包问题或者组合数学的母函数
①用背包来做的话用两个数组,背包容量=40000,然后把给出的数分开,正数做一次背包,负数做一次背包,数值的绝对值既是重量也是价值,然后两个数组扫一遍,有相等的话就是可以选出的数中恰好有可以组成0的,否则没有
②母函数的话只要把负指数加进来然后求系数就行

1年前

9
可能相似的问题

你能帮帮他们吗

精彩回答

Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 0.012 s. - webmaster@yulucn.com