Алгоритм для заполнения мешка максимально (это не рюкзак 0/1)

Question

Я работаю над некоторой задачей, которая требует от меня решения следующей алгоритмической проблемы:

---

- У вас есть коллекция предметов (их веса): [ w1, w2, ..., wn]
- И у вас есть сумка, вес которой: W
- Необходимо заполнить сумку максимально (заполнить как можно больше) подмножеством заданных предметов.

---

Так что этот не является Проблема «Рюкзак 0/1», поскольку мы имеем дело только с весами (у нас есть только один параметр для элемента). Поэтому я предполагаю, что он может иметь решение (Knapsack NP-complete) или какой-то алгоритм, который дает примерно правильный результат.

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

Спасибо заранее :)

Answer 1

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

Связь DP выглядит следующим образом

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

Реализация проблемы подмножества C++ для ответа на вопрос «Могу ли я заполнить сумку полностью, учитывая эти элементы?» и водитель следующего

bool ssp(const vector<int>& v, const int& N) { 

    vector<vector<int>> m(v.size() + 1 /* 1-based */, 
         vector<int>(N + 1 /* 1-based */, 0)); 

    // The line above also took care of the initialization for base 
    // cases f(i,0) = 0 and f(0,b) = 0 

    for (int i = 1; i <= v.size(); ++i) { // For each subset of elements 
    for (int b = 1; b <= N; ++b) { // For each subcapacity 
     int opt1 = m[i - 1][b]; 
     int opt2 = -1; 
     if (b - v[i - 1] >= 0) { // No caching to keep this readable 
     opt2 = m[i - 1][b - v[i - 1]] + v[i - 1]; 
     if (opt2 > b) 
      opt2 = -1; // Not allowed 
     } 
     m[i][b] = max(opt1, opt2); 
    } 
    } 

    return (m[v.size()][N] == N); 
} 

int main() { 

    const vector<int> v = { 1, 3, 7, 4 }; 
    const int N = 11; 

    cout << "Subset sum problem can be solved with the given input: " 
     << boolalpha << ssp(v, N); // true 

    return 0; 
} 

Сложность O(N⋅I), где I является количеством элементов в наборе исходного. Это псевдополиномиальная сложность.

Источник: Knapsack problem

Answer 2

Описанная проблема на самом деле не 0-1-Knapsack problem, но особый случай их, также называется проблемой Maximum Subset Sum, который мы проделали here. Это NP -полное, что означает, что это не проще, чем 0-1-Рюкзак сложным.

Это, как говорится, может быть решена любым алгоритмом оптимизации, предназначенным для задачи 0-1-Рюкзак, путем установления прибыли элемента, равной их весам. В целом, его можно решить оптимально, используя следующий алгоритм динамического программирования; s[i] обозначает размер, если i-й элемент и m - целочисленное пространство состояний, где m[i,s] обозначает максимальное значение, достигаемое с помощью элементов из элемента rage {0,...i}.

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 s[i] > j then: 
      m[i, j] := m[i-1, j] 
     else: 
      m[i, j] := max(m[i-1, j], m[i-1, j-s[i]] + s[i]) 

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

1. select any subset of the items such that there is no other 
    item which can be feasibly chosen 
2. select the largest item 
3. out of 1. and 2., choose the subset which yields the larger total size