Задан вес E пустой копилки и вес F копилки с
монетами. В копилке могут находиться монеты N видов, для каждого вида известна
ценность Pi и вес Wi одной монеты. Найти
минимальную и максимальную суммы денег, которые могут находиться в копилке.
Ограничения: 1 ≤ E
≤ F ≤ 100, 1
≤ N ≤ 50,
1 ≤ Pi ≤
500, 1 ≤ Wi ≤
100, все числа целые, время 2с. [1].
Комментарии вы можете посмотреть на
12 шаге.
Приведем текст программы:
Program Problem6_6; Var n:integer; {Количество видов монет} e,f:integer; {Вес пустой копилки и вес копилки с монетами} p,w:array[1..50] of word;{Ценность и вес монет} i,j,l:integer; min,max,m:longint; sum:array[0..100] of longint;{Сумма денег в копилке} lo:array[0..100, 1..50] of byte;{Какие монеты в копилке} wes:integer; Begin clrscr; {-------------- Ввод данных ---------} Repeat{Проверка – удовлетворяет ли условию задачи} write('Введите вес пустой копилки (1..100): '); readln(e); write('Введите вес копилки с монетами (1..100): '); readln(f); Until (e >= 1) And (f >= e) And (f <= 100); Repeat{Проверка} write(' Введите количество видов монет (1..50): '); readln(n); Until (n>=1) And (n<=50); writeln(' Введите ценность и вес монет:'); For i:= 1 To n Do{Ввод цены и веса монет} Begin Repeat{Проверка} write('Цена ',i,' монеты: '); readln(p[i]); Until (p[i]>0) And (p[i]<=500); Repeat{Проверка} write('Вес ',i,' монеты: '); readln(W[i]); Until (w[i]>0) And (w[i]<=100); end; {---------- Ввывод на экран введенных данных ---------} clrscr; writeln('Вес монет в копилке равен: ',f-e); writeln('Виды монет, которые могут быть в копилке (номер, ценность, вес):'); For i:= 1 To n Do{Вывод цены и веса монет} writeln(i,' ',p[i],' ',w[i]); {---------- Поиск минимальной суммы денег ---------} For i:= 0 To f-e Do{"Обнуление" матрицы lo} For j:= 1 To n Do lo[i,j]:= 0; sum[0]:= 0;{Обнуление} For wes:=1 To f-e Do{Заполнение массива sum и матрицы lo} Begin m:= -1;{Минимальная сумма} l:= 0;{Индекс в lo} For i:=1 To n Do{Может ли эта монета «поместиться» в копилку} If wes-w[i] >= 0 Then{При этом может ли копилка быть заполнена до конца} If sum[wes-w[i]] >= 0 Then {Нахождение минимальной суммы} If (m = -1) Or (sum[wes-w[i]]+p[i] < m) Then Begin m:= sum[wes-w[i]] + p[i]; l:= i;{Какую монету взяли} end; If l <> 0 Then{Если поместили монету в копилку} Begin For i:= 1 To n Do lo[wes,i]:= lo[wes-w[l],i];{Заполнение матрицы lo} lo[wes,l]:= lo[wes-w[l],l]+1;{Взяли одну монету данного вида} end; sum[wes]:= m;{Заполнение массива sum} end; min:= sum[wes];{Нашли минимальное значение} If min <> -1 Then{Если копилку можно заполнить, то выводим виды монет} Begin writeln; writeln(' Заполнение монетами копилки (сумма минимальна):'); For i:= 1 To n Do writeln(i,' -й вид монет: ',lo[wes,i]); end; {---------- Поиск максимальной суммы денег ---------} {-- Аналогично поиску минимальной суммы денег ---} For i:= 0 To f-e Do For j:= 1 To n Do lo[i,j]:= 0; sum[0]:= 0; For wes:=1 To f-e Do Begin m:= -1; l:= 0; For i:=1 To n Do If wes-w[i] >= 0 Then If sum[wes-w[i]] >= 0 Then {Отличие от поиска минимальной суммы денег} If sum[wes-w[i]]+p[i] > m Then Begin m:= sum[wes-w[i]] + p[i]; l:= i; end; If l <> 0 Then Begin For i:= 1 To n Do lo[wes,i]:= lo[wes-w[l],i]; lo[wes,l]:= lo[wes-w[l],l]+1; end; sum[wes]:= m; end; max:= sum[wes]; If min <> -1 Then Begin writeln; writeln(' Заполнение монетами копилки (сумма максимальна):'); For i:= 1 To n Do writeln(i,' -й вид монет: ',lo[wes,i]); end; writeln; {-- Вывод минимальной и максимальной суммы денег --} If (min = -1) Or (max = -1) Then {Проверка - заполнена ли копилка} writeln('Невозможно заполнить копилку!!') else Begin writeln(min,' - минимальная сумма денег в копилке'); writeln(max,' - максимальная сумма денег в копилке'); end; ReadKey; End.