Решение вариации 0/1 ранца (несколько источников для элементов, каждый элемент может быть выбран из одного из источников) - PullRequest
Новая
       12

Решение вариации 0/1 ранца (несколько источников для элементов, каждый элемент может быть выбран из одного из источников)

4 голосов
/ 21 марта 2011

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

А именно, 

S1={(d_k, b_k) | 1 ≤ k ≤ n},
S2={(d_k, b_k) | n + 1 ≤ k ≤ 2n},
S3={(d_k, b_k) | 2n + 1 ≤ k ≤ 3n},
S4 = {(d_k, b_k) | 3n + 1 ≤ k ≤ 4n}

для n = 10, если вы выберете i = 16 для ввода, это означает, что вы не выберете 6, 26 or 36 ...

Можете ли вы помочь мне решить эту проблему и разработать уравнение повторения?

Ответы [ 2 ]

8 голосов
/ 21 марта 2011

У нас есть 4n элементов.

Обозначения:

  • V[k] - значение элемента k (1 <= k <= 4n) </li>
  • W[k] - вес элемента k (1 <= k <= 4n) </li>
  • B - предел
  • f(k,B) - значение оптимального решения приграница B, и у вас есть 4k элементов.

Для элемента kth у нас есть пять возможных вариантов:

  1. Не вставлять элемент kth врюкзакПри этом ограничении значение оптимального решения составляет f(k-1,B).Зачем?потому что у нас есть еще k-1 элементов, а граница по-прежнему B.
  2. Взятие k-го элемента из S1.При этом ограничении значение оптимального решения составляет V[k] + f(k-1, B - W[k]).Зачем?Мы заработали V [k] для k-го элемента и талили W [k].Таким образом, для остальных элементов мы собираемся заработать f (k-1, B - W [k]).
  3. Взяв k-й элемент из S2.Используйте ту же логику, что и раньше, чтобы увидеть, что значение оптимального решения при этом ограничении равно V[k+n] + f(k-1, B - W[k+n]).
  4. Извлечение n-го элемента из S3.оптимально: V[k+2n] + f(k-1, B - W[k+2n]).
  5. Взятие n-го элемента из S4.оптимально: V[k+3n] + f(k-1, B - W[k+3n]).

Ваша цель - максимизировать f.Следовательно, рекуррентное уравнение: 

f(k, B) =
   max { 
        f(k-1,B),                      //you don't take item n
        V[k]    + f(k-1, B - W[k]),    //you take item k from S1
        V[k+n]  + f(k-1, B - W[k+n]),  //you take item k from S2
        V[k+2n] + f(k-1, B - W[k+2n]), //you take item k from S3
        V[k+3n] + f(k-1, B - W[k+3n])  //you take item k from S2
   }

Осталось найти начальные условия.

3 голосов
/ 21 марта 2011

Стандартная проблема ранца 0/1: Для каждого предмета, либо вы не берете его, либо вы берете.

Ваша проблема: За каждый предмет вы либо не берете его, либо берете его из источника 1, либо ..., либо берете его из источника 4.

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

(Если я немного загадочен, это потому, что это домашнее задание, а ты должен учиться: -).)

...