Условие
Попав в пещеру с сокровищами, наш Алладин не стал брать старую почерневшую лампу. Он кинулся собирать в свой рюкзак золотые монеты и драгоценные камни. Он бы, конечно, взял все, но чудес не бывает — слишком большой вес рюкзак может просто не выдержать.
Много раз он выкладывал одни вещи и на их место помещал другие, пытаясь как можно выше поднять стоимость взятых драгоценностей.
Требуется определить максимальную стоимость груза, который Алладин может поместить в свой рюкзак.
Будем считать, что в пещере имеются предметы $n$ различных типов, количество предметов каждого типа не ограничено. Максимальный вес, который может выдержать рюкзак, равен $w$. Каждый предмет типа $i$ имеет вес $w_{i}$ и стоимость $v_{i}$ $(i = 1, 2, \ldots, n)$.
Входные данные
В первой строке содержится два натуральных числа $w$ и $n$ $(1 \leqslant w \leqslant 250, 1 \leqslant n \leqslant 35)$ — максимальный вес предметов в рюкзаке и количество типов предметов. Следующие $n$ строк содержат по два числа $w_{i}$ и $v_{i}$ $(1 \leqslant w_{i} \leqslant 250, 1 \leqslant v_{i} \leqslant 250)$ — вес предмета типа $i$ и его стоимость.
Выходные данные
Выведите максимальную стоимость груза, вес которого не превышает $w$.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 10 2 5 10 6 19 |
20 |
| 2 | 250 35 187 100 28 109 245 142 123 83 237 78 36 172 15 248 90 24 181 137 40 233 8 99 231 128 79 132 43 217 156 104 45 191 130 113 105 225 206 5 26 120 26 119 64 138 23 147 19 202 79 54 149 185 158 79 209 88 110 133 235 209 188 230 15 220 107 164 235 137 60 167 |
4067 |
| 3 | 35 4 20 4 1 2 10 8 7 6 |
70 |
Программный код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
public class Main { public static void main(String[] args) { java.util.Scanner in = new java.util.Scanner(System.in); int w, n; int NegNum = -1; w = in.nextInt(); n = in.nextInt(); int WeiCos[][], s[]; WeiCos = new int [n][2]; s = new int [w + 1]; for(int i = 0; i < n; i++){ for(int j = 0; j < 2; j++){ WeiCos[i][j] = in.nextInt(); } } s[0] = 0; for(int j = 1; j <= w; j++){ s[j] = NegNum; } for(int i = 0; i < n; i++){ for(int j = WeiCos[i][0]; j <= w; j++){ if(s[j - WeiCos[i][0]] != NegNum && s[j] < s[j - WeiCos[i][0]] + WeiCos[i][1]){ s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1]; } } } int maxS = 0; for(int i = 1; i <= w; i++){ maxS = Math.max(maxS, s[i]); } System.out.print(maxS); } } |
Решение
Допустим $w = 9$, $n = 2$, первый предмет $w_{1} = 3$, $n_{1} = 4$, а второй предмет $w_{2} = 2$, $n_{2} = 1$. После того как считаем условие в два одномерных или один двумерный массив (как вам удобнее). Создадим одномерный массив в котором его размер будет равен $w$ и первый элемент будет равен 0, а остальные будут равны минус бесконечности или как в нашем случае (в коде) -1, как показано на (рис. 1). И дальше как показано на (рис. 2) начиная с элемента с номером веса предмета мы прибавляем его стоимость к стоимости предыдущей как показано в коде s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];, если прошлый не минус бесконечность. И так же со вторым элементом, когда они пересекаются с первым мы их сравниваем и вписываем в массив, больший. И в самом конце проходим заново массив и выбираем самый больший элемент, где бы он ни был как показано на (рис. 3). И таким образом на последних позициях которые равняются весу, будут записаны самые дорогие комбинации, благодаря записи самых дорогих элементов в ячейки.
Ссылки:
Задача на e-olymp
Код на OnlineGDB
Код на Ideone
Засчитанное решение на e-olymp