在论坛上看见的一个题，花时间想了下，给出一个大致的思路，记录在这里，以便以后查看
题目：
给出一堆硬币，将其分为两堆，使得这两堆的差值尽量小
1.要使得差值尽量小，等同于寻找出一个集合，它的和尽量靠近硬币和Sum/2
2.背包即可
行--每一枚硬币的选取
列--所选硬币的和的最优值
伪代码如下
SUM_OF_ALL_CIONS
half = SUM_OFALL_CIONS / 2;
memset(sum, false, sizeof(sum));
for i: 1 to coins
for j: half to 0
if sum[j] != 0
sum[j + coins_num] = true;
find the one which is true and nearest to half
阅读(925) | 评论(0) | 转发(0) |
