The task of the piggy bank with coins

Standard task on DP. Here is the solution:

• let f [i] be the maximum amount we can collect with some coins, so their total weight is i.
• Obviously, f [0] = 0.
• Fill in the values ​​of all the cells in the array f minus infinity (-maxlongint).
• Let us run over the indices of the array f starting from 0. Let the current index in the array f be equal to i. If f [i]! = Maxlongint (! = This is not equal), then we were somehow able to gain weight i. Then we go through all the coins (index j) and try to "shove" it into our DP. Those. if f [i + w [j]] <f [i] + p [j] (if we add our coin (the total weight is then equal to i + w [j]), then if the amount that was collected before (equal to f [i + w [j]]), less than the one we can get by adding to the current amount of the new coin (f [i] + p [j])), then we update our answer for this weight: f [i + w [j]] = f [i] + p [j];

Now, if in f [WITH_W - WITHOUT_W] == -maxlongint, then we could not collect the required amount, therefore This is impossible. (WITH_W, WITHOUT_W - weight of the piggy bank With and without coins)

Similarly, to find the minimum amount.

Here is an example solution in javascript. Can be checked in the browser

 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.');