weixin_47261246
weixin_47261246
2020-06-27 21:36

怎样用python实现将一组数尽可能均匀地分成两堆,使两个堆中的数的和尽可能相等?

10
  • python

麦克叔叔去世了,他在遗嘱中给他的两个孙子阿贝和鲍勃留下了一堆珍贵的口袋妖怪卡片。遗嘱中唯一的方向是“尽可能均匀地分配纸牌的价值”。作为Mike遗嘱的执行人,你已经为每一张口袋妖怪卡片定价,以获得准确的货币价值。你要决定如何将口袋妖怪卡片分成两堆,以尽量减少每一堆卡片的价值总和的差异。
例如,你有下列n=8 个口袋妖怪卡片:
图片说明

经过大量的工作,你发现你可以用下面的方法来划分卡片:
图片说明

这给了安倍10美元的牌给了鲍勃11美元的牌。这是最好的除法吗?
你要做的是解决n张牌的问题其中每张牌ci都有一个正整数值vi.你的解决方法是计算牌应该如何被分割以及每摞牌的价值。
输入输出示例如下:
图片说明

1.通过检查所有可能的桩以蛮力解决此问题。 对这种蛮力算法的时间复杂度进行分析,并通过实施和实验验证您的分析结果(既写出来算法的设计思路等),并用python算法实现编程

2.通过动态编程开发更有效的算法。 您应该首先通过动态编程的思想来分析此问题,并编写相应的递归属性。 对这种算法的时间复杂度进行分析,并通过实施和实验验证您的分析结果。并用python代码实现动态编程

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

4条回答