Создание списка всех возможных процентов предметов?

Question

Моя цель - предоставить программе несколько элементов (строк), диапазон и целевой процент, и пусть это даст мне все возможные проценты каждого элемента. Например, представьте, что вы идете в продуктовый магазин и имеете корзину яблок. & Груши вы хотите знать все проценты, которые вы могли бы использовать, используя ВСЕ предметы (не полное решение, я делаю это вручную): {Apple:50, Pears:50}, {Apple:75, Pears:25}, {Apple:90, Pears:10},etc.

Если я делаю то же самое с диапазоном 20-50 (что означает, что наибольшее значение может иметь один элемент, равный 50% и самый низкий 20%), то единственный результат: {Apple:50, Pears:50} (поскольку есть только 2 элемента и он не может превышать 50% веса)

Я думал, что у него были сходные черты, такие как проблема с рюкзаком, с несколькими большими отличиями, так как нет никаких значений/весов, связанных с предметами (но, как проблема ранца, пытающихся поместить предметы в рюкзак Я пытаюсь установить значения в пределах target_percent, 100%). У меня также возникают проблемы с применением общих идей динамического программирования, так как я не могу понять, как разрушить проблему (типичные проблемы с ранцами создают результаты, а затем результаты «кеша» для повторного использования, но если у меня есть список X элементы, мне нужно все X элементов, которые будут использоваться в пределах диапазона).

Я могу сделать это с помощью грубой силы, но я не чувствую, что он эффективен, потому что он просто пытается все, поэтому границы, которые я использую, не используются, чтобы сделать его эффективным вообще (например, если яблоко 75%, тогда нет причин, по которым груша должна превышать 25%. Ограничения - это размер списка, диапазона и target_percent. У меня может быть 20-30 элементов списка с диапазоном 5-20 или, может быть, 50 предметов с диапазоном от 1- 5 .. или все, что между ними, я хочу поиграть с тем, сколько полных результатов я могу получить как можно быстрее. Я не показал часть target_percent в вопросе, потому что я могу настроить его, чтобы как только я понял, как решить проблему , но в основном все примеры предполагают 100% макс, но иногда у вас может уже быть 20% апельсинов в вашей корзине и посмотреть, как вы можете использовать Яблоки/Груши, чтобы заполнить остальные 80%).

Мои вопросы: как я могу подходить к этому (любая логика идей для использования, примеры или проблемы с прокси-серверами, которые я могу найти)? Является ли динамическое программирование подходящим для этой проблемы или тем фактом, что я не могу сломать это на более мелкие патроны? (Помните, потому что он всегда включает в себя все элементы в списке, а не наращивание)? Если кто-то может указать мне в правильном направлении, я готов изучить любые темы, которые могут помочь (проведя 2 дня, пытаясь понять это, я просто не уверен, правильный ли маршрут динамического программирования). Также есть имя для этого типа проблемы (я искал проблемы с ранцами, целое разделение, комбинаторика, но ни один из них, казалось, не соответствовал)?

Вот мой (прерывистая) перебором подход (его на самом деле не работает, как ожидалось, но, возможно, дает представление о методе грубой силы):

import java.util.ArrayList; 
import java.util.Arrays; 


public class brute_force_percent_returner { 
    static String[] data = new String[]{"Apple", "Pears"}; 
    static int[] coeff = new int[data.length]; 
    static ArrayList<int[]> queue = new ArrayList<int[]>(); 

    public static void main(String[] args) { 
     System.out.println("Starting"); 
     recursion(0,data); 
     for (int[] item : queue) { 
      for (int item2 = 0; item2<data.length; item2++) { 
       System.out.print(data[item2] + " = " + item[item2] + " "); 
      } 
      System.out.println(); 
     } 
    } 

    private static void recursion(int k, String[] data2) { 
     // this is not exactly working 
     for (String item: data2) { 
      for (int x = 0; x<5;x++) { 
       int[] coeff_temp = Arrays.copyOf(coeff, coeff.length); 
       coeff_temp[k] = x; 
       queue.add(coeff_temp); 
      } 
     } 
     if (k == data.length-1) { 
      return; 
     } else { 
      recursion(k+1, data2); 
     } 
    } 
} 

Если это помогает решение, которое я пытался создать было в некоторой степени основанный на этом (проблема с рюкзаком, но, похоже, очень быстро для большого числа переменных, но в этом отношении элементы, которые его обрабатывают, являются элементами в списке, тогда как в моем случае список - это просто строки):

public class TurboAdder { 
    private static final int[] data = new int[] { 5, 10, 20, 25, 40, 50 }; 

    private static class Node { 
     public final int index; 
     public final int count; 
     public final Node prevInList; 
     public final int prevSum; 
     public Node(int index, int count, Node prevInList, int prevSum) { 
      this.index = index; 
      this.count = count; 
      this.prevInList = prevInList; 
      this.prevSum = prevSum; 
     } 
    } 

    private static int target = 100; 
    private static Node sums[] = new Node[target+1]; 

    // Only for use by printString. 
    private static boolean forbiddenValues[] = new boolean[data.length]; 

    public static void printString(String prev, Node n) { 
     if (n == null) { 
      System.out.println(prev); 
     } else { 
      while (n != null) { 
       int idx = n.index; 
       // We prevent recursion on a value already seen. 
       if (!forbiddenValues[idx]) { 
        forbiddenValues[idx] = true; 
        printString((prev == null ? "" : (prev+" + "))+data[idx]+"*"+n.count, sums[n.prevSum]); 
        forbiddenValues[idx] = false; 
       } 
       n = n.prevInList; 
      } 
     } 
    } 

    public static void main(String[] args) { 
     for (int i = 0; i < data.length; i++) { 
      int value = data[i]; 
      for (int count = 1, sum = value; count <= 100 && sum <= target; count++, sum += value) { 
       for (int newsum = sum+1; newsum <= target; newsum++) { 
        if (sums[newsum - sum] != null) { 
         sums[newsum] = new Node(i, count, sums[newsum], newsum - sum); 
        } 
       } 
      } 
      for (int count = 1, sum = value; count <= 100 && sum <= target; count++, sum += value) { 
       sums[sum] = new Node(i, count, sums[sum], 0); 
      } 
     } 
     printString(null, sums[target]); 

    } 
} 

Answer 1

Это звучит как домашнее задание, поэтому я неохотно помогаю вам слишком много, но вот подход.

определить диапазоны, сделать пару хэш-карты, как

lower bounds = {apples => 20, pears => 40, oranges => 0} 
upper bounds = {apples => 50, pears => 100, oranges => 30} 

, если вы об этом думаете, каждый окончательный (действительный) сочетание будет по крайней мере, имеют содержание определяется нижняя граница карты , поэтому назовите эту базовую комбинацию.

Далее, вычислите теоретический максимум каждого типа, который вы можете добавить к базовой комбинации. это просто еще одна карты

{apples => 30, pears => 60, oranges => 30} 

фигуры, сколько общих элементов, которые можно добавить в базовую карту, которая является 100 - сумма всех значений ниже связанных, в примере его 40.

сейчас, вам нужно сгенерировать комбинации. Вероятно, вы найдете рекурсию самым простым способом сделать это. плохо демонстрируют оставшийся алгоритм с псевдокодом и жестко закодированным материалом, чтобы улучшить ясность, хотя вам нужно будет написать общую, рекурсивную версию.

totalItemsToAdd = 40 //as calculated via baseCombo.sumOfEntries() 


for (i=0; i<maxApples; i++) { 
    combo = clone the base combination 
    combo.apples += i; 
    remainingItemsToAdd = totalItemsToAdd - i; 
    if (remainingItemsToAdd > 0) { 
     for (j=0; j<maxPears; j++) { 
      combo.pears += j; 
      // and so on, recursively 
     } 
    } 

    results.append(combo) 
} 

Обратите внимание, что он генерирует только действующие комбинации, отслеживая количество возможных элементов для каждой из комбинаций. Таким образом, это не было бы грубой силой, и на самом деле это выполнило бы минимальную работу, необходимую для создания набора комбинаций.

Answer 2

Я довольно уверен, что грубая сила ach - лучший способ пойти - по крайней мере, так я бы это сделал (что ни в коем случае не одно и то же ...).

Вот попытка работать с рекурсивным подходом, который у меня работает (хотя я не тестировал его с высокими значениями для weightsNo. Это работает на основе того, что вас интересуют комбинации весов, а чем перестановки весов - хотя переключатель относительно прост.

public static Set<int[]> getPossiblePercentageWeights(int weightsNo, int min, int max){ 
    return recusiveFixWeight(weightsNo, 100, min, max); 
} 

private static Set<int[]> recusiveFixWeight(int weightsNo, int sum, int min, int max){ 
    Set<int[]> weightsSet = new LinkedHashSet<int[]>(); 
    if (weightsNo>2){ 
    for (int iWeight=min; iWeight<=max; iWeight++){ 
     Set<int[]> subSet = recusiveFixWeight(weightsNo-1, sum-iWeight, min, iWeight); 
     for (int[] subWeights : subSet){ 
     int[] weights = new int[weightsNo]; 
     weights[0] = iWeight; 
     System.arraycopy(subWeights, 0, weights, 1, subWeights.length); 
     weightsSet.add(weights); 
     } 
    } 
    } else { 
    int iMax = Math.min(max, sum/weightsNo); 
    for (int iWeight=min; iWeight<=iMax; iWeight++){ 
     int jWeight = sum-iWeight; 
     if (jWeight>=min && jWeight<=max){ 
     weightsSet.add(new int[]{iWeight,jWeight}); 
     } 
    } 
    } 
    return weightsSet; 
} 

Это сказал, посмотрев на результаты, похоже, должен быть алгоритм, чтобы определить, сколько weightSets там дали weightsNo, min и max, и оттуда он должен быть достаточно простым, чтобы заполнить те, с возможными значениями. Тем не менее, я не могу сейчас это понять. (Или, действительно, будет ли это быстрее, чем подход грубой силы ...)