求算法.给出n个数,要求分成两组:(1):求两组和的差最小的分法:(2):两...求算法.给出n个数,要求分成两组:(1):求两组和的差最小的分法:(2):两组和的差最大,但不能大于这些数中的最大数(可以等于
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/25 14:05:17
求算法.给出n个数,要求分成两组:(1):求两组和的差最小的分法:(2):两...求算法.给出n个数,要求分成两组:(1):求两组和的差最小的分法:(2):两组和的差最大,但不能大于这些数中的最大数(
求算法.给出n个数,要求分成两组:(1):求两组和的差最小的分法:(2):两...求算法.给出n个数,要求分成两组:(1):求两组和的差最小的分法:(2):两组和的差最大,但不能大于这些数中的最大数(可以等于
求算法.给出n个数,要求分成两组:(1):求两组和的差最小的分法:(2):两...
求算法.
给出n个数,要求分成两组:
(1):求两组和的差最小的分法:
(2):两组和的差最大,但不能大于这些数中的最大数(可以等于).
求算法.给出n个数,要求分成两组:(1):求两组和的差最小的分法:(2):两...求算法.给出n个数,要求分成两组:(1):求两组和的差最小的分法:(2):两组和的差最大,但不能大于这些数中的最大数(可以等于
(1):求两组和的差最小的分法:
这个问题可以转换成背包问题,两组数差值最小时,则他们值相等,设他们的和为sum,可以转换为用这堆数去填一个容积为sum/2的包包,尽量填满(如果你不懂背包问题的话~上网查吧,几句话说不清).
(2):两组和的差最大,但不能大于这些数中的最大数(可以等于)
同理,也是用背包,设和为sum,最大数为max,则相差最大时,两组的和分别是(sum+max)/2 和 (sum-max)/2,这样的话,任何一组背包的值都在 (sum-max)/2 (sum+max)/2 之间,就可以转换成尽量填满一个容积为(sum+max)/2 的包包,最后的值一定大于 sum/2,因为如果小于,则另一组一定大于.