Вам предстоит длительное путешествие на автомобиле. К сожалению, у Вас в машине есть только магнитофон, а лучшая музыка записана на компакт дисках. У Вас есть чистая магнитофонная лента с длительностью звучания [latex]N[/latex] минут. Вам нужно выбрать песни для записи на магнитофонную ленту таким образом, чтобы не используемое на ней место было минимально.
Предположения:
- количество треков на CD не превышает [latex]100[/latex]
- ни один трек не длится более [latex]N[/latex] минут
- длина каждого трека выражена целым числом
- [latex]N[/latex] также целое [latex](0\leq[/latex][latex]N\leq[/latex][latex]200)[/latex]
Программа должна найти максимально возможную длину записи треков на ленту с соблюдением того же порядка треков, что и на CD.
Входные данные
Входные данные содержат несколько строк. В каждой строке сначала задано число [latex]N[/latex], далее количество треков и длительность звучания каждого трека. Все числа разделены пробелами. Например, в первой строке входных данных первым задано [latex]N=5[/latex], далее количество треков [latex]s=3[/latex], первый трек имеет длительность [latex]1[/latex] минуту, второй — [latex]3[/latex] минуты, и последний — [latex]4[/latex] минуты.
Выходные данные
Выведите строку «sum:» и далее продолжительность записи.
| Входные данные | Выходные данные |
| 5 3 1 3 4 10 4 9 8 4 2 20 4 10 5 7 4 90 8 10 23 1 2 3 4 5 7 45 8 4 10 44 43 12 9 8 2 |
sum:5 sum:10 sum:19 sum:55 sum:45 |
Код:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <cstdio> using namespace std; short d[210][110]; short arr[110]; short max (short a, short b) { return a<b ? b : a; } int main() { int n; while (scanf("%d", &n)>0){ int k; scanf("%d", &k); for (int i=1; i<=k; i++) scanf("%d", &arr[i]); for (int i=1; i<=k; i++) for (int j=0; j<=n; j++) if (arr[i]<=j) d[j][i]=max(d[j][i-1], arr[i]+d[j-arr[i]][i-1]); else d[j][i]=d[j][i-1]; printf("sum:%d\n", d[n][k]); } return 0; } |
|
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 |
import java.util.*; import java.lang.*; import java.io.*; class CD { public static void main (String[] args) throws java.lang.Exception { int[][] d = new int[210][110]; short[] arr = new short[110]; Scanner in = new Scanner(System.in); while (in.hasNext()){ short n = in.nextShort(); short k = in.nextShort(); for (int i=1; i<=k; i++) arr[i] = in.nextShort(); for (int i=1; i<=k; i++) for (int j=0; j<=n; j++) if (arr[i]<=j){ if (d[j][i-1]< arr[i]+d[j-arr[i]][i-1]) d[j][i]=arr[i]+d[j-arr[i]][i-1]; else d[j][i]=d[j][i-1]; } else d[j][i]=d[j][i-1]; System.out.printf("sum: " + d[n][k]); } } } |
Алгоритм решения построен на методе динамического программирования.
Возможны два варианта:
- Либо трек не попал на диск, следовательно длинна уже записанных треков на диск [latex](d[j][i])[/latex] равна предыдущему числу ранее записанных треков [latex](d[j][i-1])[/latex].
- Либо трек попал на диск, а значит [latex]d[j][i][/latex] равно максимуму из суммы ранее записанных треков [latex](d[j][i-1])[/latex] и суммы заданной длинны [latex]arr[i][/latex] c [latex]d[j-arr[i]][i-1]][/latex], где [latex]d[j-arr[i]][i-1]][/latex] равен сумме уже записанных треков при предыдущем элементе массива [latex]arr[i-1][/latex]
Принято. Оценку выставил.
Не вижу ссылки на засчитанное на Java решение. 5 баллов.