Получить самую дешевую комбинацию элементов в массиве для достижения заданного значения - PullRequest
Новая
       17

Получить самую дешевую комбинацию элементов в массиве для достижения заданного значения

0 голосов
/ 20 мая 2019

Я пытаюсь решить проблему с комбинациями:

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

Учитывая следующую проблему: 

[{
  "name": "network 1",
  "availability": 0.5,
  "cost": 20, 
 },               
 {
  "name": "network 2",
  "availability": 0.75,
  "cost": 30,
 }]

Мне нужно найти наиболее эффективную и дешевую комбинацию, используя следующее уравнение для расчета доступности: 1 - (1 - availability A) * (1 - availability B)… * (1 - availability n)

Требования / правила:

  • Общая доступность составляет 0,9999 (т. Е. 99,99%)
  • Допускается повтор
  • Должна быть самая дешевая комбинацияcost -wise

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

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

В конце я вернулся к неограниченному ранцу, так как в нем есть повторы иЯ получил это до сих пор: 

private static int max(int i, int j) {
        return (i > j) ? i : j;
    }

    private static int unboundedKnapsack(int W, int n, List<Long> val, List<Long> wt) {
        int dp[] = new int[W + 1];

        for(int i = 0; i <= W; i++){
            for(int j = 0; j < n; j++){
                if(wt.get(j) <= i){
                    dp[i] = max(dp[i], Math.toIntExact(dp[(int) (i - wt.get(j))] + val.get(j))); // TODO: can't figure out how to implement 1 - (1 - availability A) * (1 - availability B)… * (1 - availability n) instead.
                }
            }
        }

        return dp[W];
    }

    public static void main(String[] args) {
        String problem = "" +
                "[{\"function\":\"Server\", " +
                "\"name\":\"server 1\", " +
                "\"availability\":5, " +
                "\"cost\":10 }, " +

                "{\"function\":\"Server\", " +
                "\"name\":\"server 2\", " +
                "\"availability\":10, " +
                "\"cost\":30 }, " +

                "{\"function\":\"Server\", " +
                "\"name\":\"server 3\", " +
                "\"availability\":15, " +
                "\"cost\":20 }] ";

        JSONParser parser = new JSONParser();

        try{
            Object obj = parser.parse(problem);
            JSONArray array = (JSONArray) obj;

            List<Long> valArray = new ArrayList<>();
            List<Long> wtArray = new ArrayList<>();
            for (Object value : array) {
                JSONObject o = (JSONObject) value;

                Long cost = (Long) o.get("cost");
                valArray.add(cost);

                Long availability = (Long) o.get("availability");
                wtArray.add(availability);

            }

            int W = 100; // TODO: should be the required availability i.e 0.9999. Can't figure out how to get it to work with double values
            int n = valArray.size();
            System.out.println("cost: " + unboundedKnapsack(W, n, valArray, wtArray));
        } catch(ParseException pe) {
            System.out.println("position: " + pe.getPosition());
            System.out.println(pe);
        }
    }

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

cost: 300

Однако вывод, который я пытаюсь получить, выглядит примерно так: 

availability: 0.9999
items: server 1, server 2...
cost: 300

Если у кого-то есть идеяалгоритм исправить это, я был бы очень признателен.

1 Ответ

0 голосов
/ 21 мая 2019

Эту проблему можно решить с помощью динамического программирования, используя идею, аналогичную предложенной в . Существует ли какой-либо алгоритм для решения самой длинной общей последующей проблемы с разными весами для каждого символа? .

Идея состоит в том, что вы создаете таблицу записей, упорядоченных по возрастанию стоимости и доступности. Каждая запись содержит следующие данные: 

total_cost: ...
total_availability: ...
last_item: ...
previous_entry:

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

Ваша таблица начинается с одной записи: 

{total_cost: 0, total_availability: 0.0, last_item: null, previous_entry: null}

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

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

Это займет время, которое является полиномиальным по количеству записей и сколько возможных затрат, которые необходимы.

...