英文:
Given an array of integers, how can I assign the ints to two different arrays that have a capacity?
问题
你被给予一个整数列表，你必须将整数添加到两个列表中的一个，这两个列表具有相同的容量，列表中的整数之和必须小于容量。
这只是我想要解决的问题的大致描述，我正在尝试将相同的逻辑应用于一个高级项目。我尝试了一种贪婪的方法，但这是一个动态规划问题，所以我需要一个更好的解决方案来处理边界情况。
英文:
You're given a list of integers, you must add the integers to one of two lists, each of these lists has the same capacity that the sum of ints inside the list must be under.
This is just a rough description of the problem I'm looking to solve, I am trying to apply the same logic to an advanced project. I tried doing a greedy approach but this is a dynamic programming problem so I need a better solution for edge cases.
答案1
得分: 1
这是一个带有2个容器的装箱问题，最坏情况下等同于一个子集和问题。
设S为数组A的总和，C为两个子列表的容量。显然，如果S > 2C，则没有解决方案。否则，S ≤ 2C，你需要找到A的一个子序列，其和介于S-C和C之间，以便其补集的和最多为C。
这是一个经典的子集和问题，你可以使用标准的动态规划算法来解决，你可以在维基百科或其他许多地方找到该算法。
英文:
This is a bin packing problem with 2 bins, which in the worst case, is equivalent to a subset sum problem.
Let S be the sum of your array A, and C the capacity of each of the two sublists. Clearly if S > 2C there can be no solution. Otherwise, S ≤ 2C and you need to find a subsequence of A whose sum is between S-C and C, so that the complement has sum at most C.
This is a classical subset sum problem that you can solve with the standard dynamic programming algorithm that you can find on Wikipedia or any number of other places.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论