Вариант рюкзака

Question

Я работаю над программой для решения варианта проблемы 0/1 Рюкзак.

Оригинальная проблема описана здесь: https://en.wikipedia.org/wiki/Knapsack_problem. В случае отсутствия ссылки в будущем, я дам вам краткое изложение проблемы 0/1 Рюкзак (если вы с ней знакомы, скачайте этот абзац): Допустим, у нас есть n предметов, каждый с весом wi и значение vi. Мы хотим поместить предметы в сумку, которая поддерживает максимальный вес W, так что общая стоимость внутри сумки максимально возможная без лишнего веса мешка. Элементы не могут иметь несколько экземпляров (т. Е. У нас есть только один). Задача проблемы заключается в maximize SUM(vi.xi), так что SUM(wi.xi) <= W и xi = 0, 1 (xi представляет состояние элемента, находящегося или не находящегося в сумке).

Для моего случая, есть небольшие различия в обоих условиях и целях:

• вес всех элементов составляет 1, wi = 1, i = 1...n

• Я всегда хочу поставить ровно половину элементов в мешок. Таким образом, максимальная грузоподъемность сумки составляет половину (округляется) от количества предметов. W = ceil[n/2] или W = floor[(n+1)/2].

• Кроме того, вес в сумке должен быть равен максимальной емкостью SUM(wi.xi) = W

Наконец, вместо максимизации стоимости предметов внутри сумки, цель состоит в том, чтобы стоимость предметов внутри как можно ближе к значению предметов снаружи. Следовательно, моя цель - minimize |SUM(vi.-xi) - SUM[vi(1-xi)]|, которая упрощается во что-то вроде minimize |SUM[vi(2xi - 1)]|.

Теперь на странице Википедии есть псевдокод исходной задачи 0/1 Рюкзак (вы можете найти ее в нижней части этого текста), но мне трудно адаптировать ее к моему сценарию. Может кто-нибудь помочь? (Я не прошу код, просто за идею, поэтому язык не имеет значения)

Спасибо!

---

Википедия псевдо-код для задачи 0/1 котомки:

Пусть w1, w2, ..., wn, W строго положительные целые числа. Определить m[i,w] как максимальное значение, которое может быть достигнуто весом менее , равным w, с использованием товаров до i (первые i штук).

Мы можем определить m[i,w] рекурсивно следующим образом:

• m[0, w]=0
• m[i, w] = m[i-1, w] if wi > w (новый пункт больше, чем текущий предел веса)
• m[i, w]= max(m[i-1, w], m[i-1, w-wi] + vi) if wi <= w.

Решение можно найти, вычислив m[n,W].

// Input: 
// Values (stored in array v) 
// Weights (stored in array w) 
// Number of distinct items (n) 
// Knapsack capacity (W) 

for j from 0 to W do: 
    m[0, j] := 0 

for i from 1 to n do: 
    for j from 0 to W do: 
     if w[i-1] <= j then: 
      m[i, j] := max(m[i-1, j], m[i-1, j-w[i-1]] + v[i-1]) 
     else: 
      m[i, j] := m[i-1, j] 

Answer 1

Благодаря @harold, кажется, что это проблема не является проблемой рюкзака, но проблема раздела. Часть псевдокода, который я искал, находится на соответствующей странице Википедии: https://en.wikipedia.org/wiki/Partition_problem

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

В результате я нашел вопрос, требующий этого (здесь: Balanced partition), с примером кода, который я тестировал и отлично работает.