0
У меня есть код, который дает максимальное значение, которое я могу получить, заполняя рюкзак оптимальным набором весов.Рюкзак - Как определить, какие весы используются?
int arr[5] = {0, 0, 0, 0, 0};
int Weight[5] = {2, 5, 8, 7, 9};
int Value[5] = {4, 5, 7, 9, 8};
const int n = 5;
const int maxCapacity = 20;
int maximum(int a, int b)
{
return a > b ? a : b;
}
int knapsack(int capacity, int i)
{
if (i > n-1) return 0;
if (capacity < Weight[i])
{
return knapsack(capacity, i+1);
}
else
{
return maximum (knapsack(capacity, i+1),
knapsack(capacity - Weight[i], i+1) + Value[i]);
}
}
int main (void)
{
cout<<knapsack(maxCapacity,0)<<endl;
return 0;
}
Мне нужно расширить это решение, распечатав все весы, чтобы найти оптимальное решение. Для этого я планирую использовать массив arr, инициализированный равным 0. Всякий раз, когда используется вес, я отмечаю соответствующее положение в arr на 1, в противном случае оно остается 0.
Первое, что пришло мне в голову, это изменить максимум (), как показано ниже
int maximum(int a, int b, int i)
{
if (a > b)
{
if (arr[i] == 1) arr[i] = 0;
return a;
}
else
{
if (arr[i] == 0) arr[i] = 1;
return b;
}
}
Но даже это решение не подходит для некоторой комбинации весов и значений. Любые предложения о том, как продвигаться вперед?
Вы можете отправить примерную комбинацию, которая терпит неудачу, это обычно очень показательно. –
PS: вы должны рассмотреть замену этих массивов на 'std :: array', если вы используете C++ 11, что гораздо удобнее. –
akappa
@BartekBanachewicz: Пример массива уже жестко закодирован в коде. В этом случае будут использоваться веса - 2, 7, 9, а окончательное значение arr [5] равно {1, 1, 0, 1, 1}, где должно быть {1, 0, 0, 1, 1} – bibbsey