Вариант ранца

Я работаю над программой для решения одного из вариантов задачи о рюкзаке 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]