Почему этот алгоритм для целочисленного рюкзака неверен?

Это то, что я думаю, что мне нужно сделать.

Имея «n» предметов веса «Wi» и значения «Vi», мне нужно максимизировать стоимость рюкзака, оставаясь при этом ниже предела веса WEIGHT_MAX.

Итак, я подумал о том, чтобы сортировать предметы в соответствии с их ценностью (от большего к меньшему), а затем выбирать предметы, если вес рюкзака меньше WEIGHT_MAX.

то есть что-то вроде этого

while( temp_weight <= WEIGHT_MAX && i <= INDEX_MAX )
{
   if ( temp_weight + W[i] > WEIGHT_MAX ) { i++; continue;}
   temp_weight += W[i];
   value += V[i];
   i++;
}

Почему этот алгоритм неверен?


knapsack-problem dynamic-programming
person user2441151    schedule 15.01.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Рассмотрим эти отсортированные элементы:

Vi={10, 5, 5, 5, 5, 5, 5}

Wi={4, 1, 1, 1, 1, 1, 1}

С вашим алгоритмом, если ваш WEIGHT_MAX равен 4, вы бы выбрали только элемент V = 10 (общее значение 10). Но оптимальным решением будет 4 элемента с V=5 (общее значение 20).

Поэтому ваш алгоритм не приводит к оптимуму.

Несколько алгоритмов для ее решения: http://en.wikipedia.org/wiki/Knapsack_problem

person jbgs    schedule 15.01.2014
comment
Ой! Большое спасибо за помощь. Тогда не стоит ли подумать о сортировке массива по соотношению Vi/Wi? В чем здесь будет ошибка? - person user2441151; 15.01.2014
comment
Взгляните на статью в Википедии. Это не так просто, как вы думаете :) Я использую подход линейного программирования (с GLPK) для решения подобных задач. Но другие алгоритмы могут быть лучше с точки зрения производительности. - person jbgs; 15.01.2014