use*_*919 6 arrays dynamic-programming
我在编码比赛中遇到了这个问题 -
你得到一个正整数数组,并允许你随时改变任何整数的符号.编写程序来计算该数组的最小总和.这个总和应该> = 0.例如:Array = {1,2,4,5}然后sum = 0,因为我们改变了1和5的符号{-1,2,4,-5}
我对这个问题的解决方案是对数组进行排序并找到所有成员的总和.然后,我将从最大数字开始迭代地减少2*(排序数组值) - 直到sum变为0或直到它变为负数.
但我的解决方案是错误的.拿12,13,14,15,16,50.我的代码会将50更改为-50并停止(即最小总和= 20).但答案应该是12,-13,-14,-15,-16,50(最小值= 4)
这个问题可以改成一个傻瓜问题
考虑这个问题:
你得到n个整数,显然,你可以计算这些数的总和,假设它是S.
您现在需要从中选择一组数字,并且旨在将这些选定的数字加起来尽可能接近S/2
这可以使用DP算法来完成,这与knap-sack问题非常相似
你能现在做吗？:)
这篇文章只是一个提示,如果你需要更多帮助,我可以提供更多细节
| 归档时间： |
|
| 查看次数： |
5405 次 |
| 最近记录： |