Нахождение наибольшего подмножества с суммой, равной или меньшей заданного числа, без рекурсии

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}. Затем вы просто продолжаете добавлять элемент в список, пока сумма меньше, чем бюджет.Java:

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

Итак, вот ситуация: я написал программу, которая использует рекурсию и выполняет то, что вы ищете. Единственное, что он улавливает самую длинную комбинацию (и) / подмножество (ы) чисел, которые в точности равны целевой сумме (6 в вашем примере); Я не мог понять, как найти самое длинное подмножество, которое было меньше или равно целевой сумме. Кроме того, в вашем примере у вас есть два 1 по цене. Если вы запустите экземпляр моей программы, вы заметите, что он будет обрабатывать два подмножества (более одного поднабора равным 6) как имеющие одинаковый идентификатор для 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"); 
             }
          }
       }
    } 
}

Answer 3

Как сказал Джордан в комментариях, жадное решение подойдет.Предполагая, что отсортировано список 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
}

Добавляя сначала самые дешевые продукты, вы гарантируете, что сможете уместить как можно больше, прежде чем попадать в бюджет.