Алгоритм ранца для двух сумок

Question

Алгоритм ранца для двух сумок

я обнаружил нить который предоставляет псевдокод для алгоритма ранца с двумя ранцами.
Я пытался реализовать его в C ++, но он не работает, как предполагалось. Вот код:

#include <cstdio>
#define MAX_W1 501
#define MAX_W2 501

int maximum(int a, int b, int c) {
int max = a>b?a:b;
return c>max?c:max;
}

int knapsack[MAX_W1][MAX_W2] = {0};

int main() {
int n, s1, s2, gain, weight; // items, sack1, sack2, gain, cost

scanf("%d %d %d", &n, &s1, &s2);

// filing knapsack
for (int i = 0; i < n; i++) {
scanf("%d %d", &gain, &weight);

for (int w1 = s1; w1 >= weight; w1--) {
for (int w2 = s2; w2 >= weight; w2--) {
knapsack[w1][w2] = maximum(
knapsack[w1][w2],                 // we have best option
knapsack[w1 - weight][w2] + gain, // put into sack one
knapsack[w1][w2 - weight] + gain  // put into sack two
);
}
}
}

int result = 0;

// searching for result
for (int i = 0; i <= s1; i++) {
for (int j = 0; j <= s2; j++) {
if (knapsack[i][j] > result) {
result = knapsack[i][j];
}
}
}

printf("%d\n", result);

return 0;
}

Например, для следующего ввода:

У меня есть вывод:

Очевидно, что это неправильно, потому что я могу взять все предметы (1,2 в первую сумку и остаток во вторую сумку), и сумма равна 16.
Я был бы благодарен за любое объяснение, где я неправильно понимаю псевдокод.

Я сделал небольшое обновление с тех пор, у некоторых людей есть проблемы с пониманием формата ввода:

Первая строка содержит 3 числа: количество предметов, вместимость мешка один, вместимость мешка два
Далее есть n строк, каждая из которых содержит 2 числа: выигрыш, стоимость i-го предмета.
Предположим, что мешки не могут быть больше 500.

2

algorithm c++knapsack-problem

Решение

Другие решения

Вот модификация кода, чтобы он работал: —

#include <cstdio>
#define MAX_W1 501
#define MAX_W2 501

int maximum(int a, int b, int c) {
int max = a>b?a:b;
return c>max?c:max;
}

int knapsack[MAX_W1][MAX_W2] = {0};

int main() {
int n, s1, s2, gain, weight; // items, sack1, sack2, gain, cost

scanf("%d %d %d", &n, &s1, &s2);

// filing knapsack
for (int i = 0; i < n; i++) {
scanf("%d %d", &gain, &weight);
// need to fill up all the table cannot stop if one sack is full because item might fit in other
for (int w1 = s1; w1 >= 0; w1--) {
for (int w2 = s2; w2 >= 0; w2--) {
int val1=0,val2=0;
if(weight<=w1)
val1 = knapsack[w1 - weight][w2] + gain;
if(weight<=w2)
val2 = knapsack[w1][w2 - weight] + gain;

knapsack[w1][w2] = maximum(
knapsack[w1][w2],                   // we have best option
val1,              // put into sack one
val2               // put into sack two
);}
}
}// No need to search for max value it always be Knapsack[s1][s2]
printf("%d\n", knapsack[s1][s2]);

return 0;
}

3

Источник

Accepted Answer

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

#include <algorithm>

using std::max;

int max3(int a, int b, int c) {
return max(a, max(b, c));
}

а также

for (int w1 = s1; w1 >= 0; w1--) {
for (int w2 = s2; w2 >= 0; w2--) {
if (w1 >= weight && w2 >= weight) // either sack has room
{
knapsack[w1][w2] = max3(
knapsack[w1][w2],                 // we have best option
knapsack[w1 - weight][w2] + gain, // put into sack one
knapsack[w1][w2 - weight] + gain  // put into sack two
);
}
else if (w1 >= weight) // only sack one has room
{
knapsack[w1][w2] = max(
knapsack[w1][w2],                 // we have best option
knapsack[w1 - weight][w2] + gain  // put into sack one
);
}
else if (w2 >= weight) // only sack two has room
{
knapsack[w1][w2] = max(
knapsack[w1][w2],                 // we have best option
knapsack[w1][w2 - weight] + gain  // put into sack two
);
}
}
}

2