数学吧 关注:851,231贴子:8,607,723
  • 5回复贴,共1

不会写,求助

只看楼主收藏回复

为什么把石头重量分成尽可能相等的两堆,这两个重量的绝对值是答案呀


IP属地:湖北来自Android客户端1楼2024-06-30 20:57回复
    可以理解为stone[i]数组元素之前任意添加+或-,使得绝对值最接近0。根据这个思路,把取+和取-的分开,其重量越接近,这个总的绝对值就越接近0。所以就是不超过二分之总重量的背包问题


    IP属地:安徽来自Android客户端2楼2024-06-30 21:36
    回复
      如果所有石头被分成两组,重量的差为m,只要每次从一组中取一块,再从另一组中取一块,那最后当某组被清空时剩下的正好是m,最终返回的结果不会超过m
      另外不管按怎样的顺序取石头,每次剩下的重量都是先前两块石头相减得到,所以最终剩下的重量也可以由一开始所有重量通过加减组合得到,相当于是某一组石头的总重减去另一组石头的总重
      所以,最后返回结果的最小取值不超过m的最小值,而返回结果的取值范围又在m的取值范围内,那说明返回结果的最小值就等于m的最小可能值


      IP属地:安徽来自Android客户端3楼2024-06-30 22:32
      收起回复
        我一眼看出这是力扣题目这题我做过


        IP属地:上海来自Android客户端4楼2024-06-30 23:08
        收起回复