Вот пример решения, на JavaScript. Можно проверить в браузере
function calc( sum, cost, weight ){
var min = [], //Массив минимальных стоимостей
max = [], //Массив максимальных стоимостей
c_cost, c_weight, //Вес/Стоимость текущей монет
c_min, c_max, //Мин/Макс стоимости для данного веса
t_min, t_max, //Мин/Макс вес который получиться при
//добавлении этой монеты
w, j, //Счётчик по весу и по монетам
mj = cost.length; //Ограничение на кол-во монет
min[0] = max[0] = 0; //Для веса 0 и 0
//Проходим по всем весам
for ( w = 1; w <= sum; w++ ){
c_min = 0; //Изначально, такого веса нельзя получить
c_max = 0; //и потому его мин и макс стоимости - 0
//Проходим по библиотеке монет
for ( j = 0; j < mj; j++ ){
c_cost = cost[j]; //Сохраняем данные
c_weight = weight[j]; //Текущей монеты
//Если вес текущей монеты равен текущему весу,
//то этот вес можно получить
if ( w == c_weight ){
//Если вес не достигался ранее, или его мин стоимость больше моей
if ( ( c_min == 0 ) || ( c_min > c_cost ) ) c_min = c_cost;
//Если макс стоимость меньше моей
if ( c_max < c_cost ) c_max = c_cost;
}
//Если вес текущей монеты больше текущему весу
else if ( w > c_weight ){
//Вычисляем какими станут мин и макс стоимости
//при добавлении этой монеты
t_min = min[ w - c_weight ] + c_cost;
t_max = max[ w - c_weight ] + c_cost;
//Если вес ( w - c_weight ) - достигается,
//то если вес не достигался ранее, или его мин стоимость больше моей
if ( ( t_min != c_cost ) &&
( ( c_min == 0 ) || ( c_min > t_min ) )
) c_min = t_min;
//Если вес не достигался ранее, или его макс стоимость меньше моей
if ( ( t_max != c_cost ) && ( c_max < t_max ) ) c_max = t_max;
}
}
//Записываем данные в память
min[ w ] = c_min;
max[ w ] = c_max;
}
return [ min[sum], max[sum], min, max ];
}
cost = [ 1, 2, 3 ];
weight = [ 2, 4, 5 ];
sum = 36;
res = calc( sum, cost, weight );
if ( res[0] && res[1] ) console.log( res[0], ' ', res[1] );
else console.log('This is impossible.');