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

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) {

    ArrayList<Product> product = new ArrayList<>();

    product.add(new Product(1, "pr1", 1));

    product.add(new Product(2, "pr2", 1));

    product.add(new Product(3, "pr3", 1.5));

    product.add(new Product(4, "pr4", 3));

    product.add(new Product(5, "pr5", 2));

    product.add(new Product(6, "pr6", 4));

    Price price = new Price();  // Custom comparator that compares two Products' price, must be defined elsewhere

    Collections.sort(product, price); 

    ArrayList<Product> longest = new ArrayList<>();

    for(int i=0; i < product.size(); i++) {

        if(budget - product.get(i).price > 0) {

            budget = budget - product.get(i).price;

            longest.add(product.get(i));

        }

    }

}

Answer 2

正如乔丹在评论中所说，贪婪的解决方案会奏效。假设一个排序列表products：

int sum = 0;

List<Product> subset = new ArrayList<>();

for (Product p : products) {

  if (sum + p.price <= budget) {

    subset.add(p);

    sum += p.price;

  } else return subset;  // or break

}

通过首先添加最便宜的产品，您可以保证在达到预算之前可以容纳尽可能多的产品。

Answer 3

所以情况是这样的：我写了一个程序，它确实使用递归并且有点完成你正在寻找的东西。唯一的问题是它捕获了最长的数字组合/子集，这些组合仅恰好等于目标总和（在您的示例中为 6）；我似乎无法弄清楚如何找到小于或等于目标总和的最长子集。此外，在您的示例中，价格有两个 1。如果您运行我的程序实例，您会注意到它会将两个子集（多于一个子集等于 6）视为具有相同的 id 1，因此它们是重复的子集。那是您可以解决的另一个问题。这个程序花了我一天多的时间才想出，所以即使它有问题并且使用递归，我还是想发布它。

import java.util.*;

public class SubSet_sum_problem

{

    private static ArrayList<int[]> listOfArrays = new ArrayList<int[]>();

    public static void getSubsets(double[] elements, double sum) {

       getAllSubsets(elements, 0, sum, new Stack<Double>());

    }

    private static void getAllSubsets(double[] elements, int i, double sum, Stack<Double> currentSol) { 

       //stop clauses:

       if (sum == 0 && i == elements.length)

       {

         Object[] prices = currentSol.toArray();

         double[] prices2 = new double[currentSol.size()];

         for (int index = 0; index < prices.length; index++)

             prices2[index] = (Double)prices[index];

         int[] indexes = new int[currentSol.size()];

         for(int index2 = 0; index2 < prices2.length; index2++) {    // Find common/duplicate elements in both arrays

            for(int count = 0; count < elements.length; count++) {

                if(prices2[index2] == elements[count])

                    indexes[index2] = count;

            }

         }

         for (int a = 0; a < indexes.length; a++)   // Scanning for duplicates again, this time for common indexes

         { 

           for (int b = a + 1; b < indexes.length; b++) 

           { 

             if (indexes[a] == indexes[b])   // Now we know we have duplicate indexes for the elements[] array, which isn't possible

             {

                indexes[a] = a;

                indexes[b] = b;

             }

           }  

         }

         listOfArrays.add(indexes);

       }

       //if elements must be positive, you can trim search here if sum became negative

       if (i == elements.length) 

         return;

       //"guess" the current element in the list:

       currentSol.add(elements[i]);

       getAllSubsets(elements, i+1, sum-elements[i], currentSol);

       //"guess" the current element is not in the list:

       currentSol.pop();

       getAllSubsets(elements, i+1, sum, currentSol);

    }

    public static void main(String args[]) 

    { 

       String name[] = {"pr1", "pr2", "pr3", "pr4", "pr5", "pr6"};

       double price[] = {1, 1, 1.5, 3, 2, 4};

       double sum = 6.0;

       getSubsets(price, sum);

       int size = listOfArrays.size();

       int max = listOfArrays.get(0).length;

       for(int str[] : listOfArrays)

       {

          int theSize = str.length;

          if(max < theSize)

            max = theSize;

       }

       for(int arr[] : listOfArrays)

       {

          if (arr.length == max)

          {

             for (int index = 0; index < arr.length; index++)

             {

                int index2 = arr[index] + 1;

                System.out.print("{id: " + index2 + ", name: " + name[arr[index]] + ", price: " + price[arr[index]] + "}\n");

                if (index == arr.length - 1)

                   System.out.print("\n"); 

             }

          }

       }

    } 

}