在没有递归的情况下找到总和等于或小于给定数的最大子集

Question

有一个Product具有属性的对象price，也给定了一个budget。

从产品列表和给定预算中，如何获得价格总和等于或小于预算的最长产品子集。每个子集只允许 1 个产品。价格和预算总是积极的

例如

   [

      {id: 1, name: pr1, price: 1},

      {id: 2, name: pr2, price: 1},

      {id: 3, name: pr3, price: 1.5},

      {id: 4, name: pr4, price: 3},

      {id: 5, name: pr5, price: 2},

      {id: 6, name: pr6, price: 4},

   ]

预算 = 6

结果

  [

      {id: 1, name: pr1, price: 1},

      {id: 2, name: pr2, price: 1},

      {id: 3, name: pr3, price: 1.5},

      {id: 5, name: pr5, price: 2},

  ]

是否可以不用递归解决这个问题

Answer 1

听起来像面试题。示例是对价格进行排序，因此您将有 {1,1,1.5,2,3,4} 然后您只需继续将项目添加到列表中，而总和小于预算。爪哇：public static void main(String[] args) {&nbsp; &nbsp; ArrayList<Product> product = new ArrayList<>();&nbsp; &nbsp; product.add(new Product(1, "pr1", 1));&nbsp; &nbsp; product.add(new Product(2, "pr2", 1));&nbsp; &nbsp; product.add(new Product(3, "pr3", 1.5));&nbsp; &nbsp; product.add(new Product(4, "pr4", 3));&nbsp; &nbsp; product.add(new Product(5, "pr5", 2));&nbsp; &nbsp; product.add(new Product(6, "pr6", 4));&nbsp; &nbsp; Price price = new Price();&nbsp; // Custom comparator that compares two Products' price, must be defined elsewhere&nbsp; &nbsp; Collections.sort(product, price);&nbsp;&nbsp; &nbsp; ArrayList<Product> longest = new ArrayList<>();&nbsp; &nbsp; for(int i=0; i < product.size(); i++) {&nbsp; &nbsp; &nbsp; &nbsp; if(budget - product.get(i).price > 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; budget = budget - product.get(i).price;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; longest.add(product.get(i));&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}

Answer 2

正如乔丹在评论中所说，贪婪的解决方案会奏效。假设一个排序列表products：int sum = 0;List<Product> subset = new ArrayList<>();for (Product p : products) {&nbsp; if (sum + p.price <= budget) {&nbsp; &nbsp; subset.add(p);&nbsp; &nbsp; sum += p.price;&nbsp; } else return subset;&nbsp; // or break}通过首先添加最便宜的产品，您可以保证在达到预算之前可以容纳尽可能多的产品。

Answer 3

所以情况是这样的：我写了一个程序，它确实使用递归并且有点完成你正在寻找的东西。唯一的问题是它捕获了最长的数字组合/子集，这些组合仅恰好等于目标总和（在您的示例中为 6）；我似乎无法弄清楚如何找到小于或等于目标总和的最长子集。此外，在您的示例中，价格有两个 1。如果您运行我的程序实例，您会注意到它会将两个子集（多于一个子集等于 6）视为具有相同的 id 1，因此它们是重复的子集。那是您可以解决的另一个问题。这个程序花了我一天多的时间才想出，所以即使它有问题并且使用递归，我还是想发布它。import java.util.*;public class SubSet_sum_problem{&nbsp; &nbsp; private static ArrayList<int[]> listOfArrays = new ArrayList<int[]>();&nbsp; &nbsp; public static void getSubsets(double[] elements, double sum) {&nbsp; &nbsp; &nbsp; &nbsp;getAllSubsets(elements, 0, sum, new Stack<Double>());&nbsp; &nbsp; }&nbsp; &nbsp; private static void getAllSubsets(double[] elements, int i, double sum, Stack<Double> currentSol) {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;//stop clauses:&nbsp; &nbsp; &nbsp; &nbsp;if (sum == 0 && i == elements.length)&nbsp; &nbsp; &nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Object[] prices = currentSol.toArray();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;double[] prices2 = new double[currentSol.size()];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (int index = 0; index < prices.length; index++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;prices2[index] = (Double)prices[index];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;int[] indexes = new int[currentSol.size()];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for(int index2 = 0; index2 < prices2.length; index2++) {&nbsp; &nbsp; // Find common/duplicate elements in both arrays&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for(int count = 0; count < elements.length; count++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(prices2[index2] == elements[count])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; indexes[index2] = count;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (int a = 0; a < indexes.length; a++)&nbsp; &nbsp;// Scanning for duplicates again, this time for common indexes&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (int b = a + 1; b < indexes.length; b++)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (indexes[a] == indexes[b])&nbsp; &nbsp;// Now we know we have duplicate indexes for the elements[] array, which isn't possible&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; indexes[a] = a;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; indexes[b] = b;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;listOfArrays.add(indexes);&nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp; &nbsp;//if elements must be positive, you can trim search here if sum became negative&nbsp; &nbsp; &nbsp; &nbsp;if (i == elements.length)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return;&nbsp; &nbsp; &nbsp; &nbsp;//"guess" the current element in the list:&nbsp; &nbsp; &nbsp; &nbsp;currentSol.add(elements[i]);&nbsp; &nbsp; &nbsp; &nbsp;getAllSubsets(elements, i+1, sum-elements[i], currentSol);&nbsp; &nbsp; &nbsp; &nbsp;//"guess" the current element is not in the list:&nbsp; &nbsp; &nbsp; &nbsp;currentSol.pop();&nbsp; &nbsp; &nbsp; &nbsp;getAllSubsets(elements, i+1, sum, currentSol);&nbsp; &nbsp; }&nbsp; &nbsp; public static void main(String args[])&nbsp;&nbsp; &nbsp; {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;String name[] = {"pr1", "pr2", "pr3", "pr4", "pr5", "pr6"};&nbsp; &nbsp; &nbsp; &nbsp;double price[] = {1, 1, 1.5, 3, 2, 4};&nbsp; &nbsp; &nbsp; &nbsp;double sum = 6.0;&nbsp; &nbsp; &nbsp; &nbsp;getSubsets(price, sum);&nbsp; &nbsp; &nbsp; &nbsp;int size = listOfArrays.size();&nbsp; &nbsp; &nbsp; &nbsp;int max = listOfArrays.get(0).length;&nbsp; &nbsp; &nbsp; &nbsp;for(int str[] : listOfArrays)&nbsp; &nbsp; &nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int theSize = str.length;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(max < theSize)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; max = theSize;&nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp; &nbsp;for(int arr[] : listOfArrays)&nbsp; &nbsp; &nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (arr.length == max)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (int index = 0; index < arr.length; index++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int index2 = arr[index] + 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print("{id: " + index2 + ", name: " + name[arr[index]] + ", price: " + price[arr[index]] + "}\n");&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (index == arr.length - 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;System.out.print("\n");&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; }&nbsp;}