Динамическое программирование

@Hyskills · Регистрация: 24.02.2016

Студворк — интернет-сервис помощи студентам

Во время трансляции концерта предприниматель решил сделать бизнес на производстве кассет. Он имеет M кассет с длительностью звучания D каждая и хочет записать на них максимальное число песен. Эти песни (их общее количество N) передаются в порядке 1, 2, …, N и имеют заранее известные ему длительности звучания L1, L2, …, LN. Предприниматель, прослушивая по порядку песни, может выполнять одно из следующих действий:

если песня на текущую кассету помещается, то он может записать ее на кассету или пропустить песню;
если песня на кассету не помещается, то он может пропустить песню или начать ее записывать на новую кассету (при этом старая кассета откладывается и туда уже ничего не может быть записано).
Необходимо определить максимальное количество песен C, которые предприниматель может записать на кассеты.

Входные данные
Входные данные содержатся в файле input.txt.

В первой строке файла находятся числа N, M и D (все числа натуральные 1 ≤ N ≤ 200, 1 ≤ M ≤ 50, 1 ≤ D ≤ 1000).
Во второй строке, находятся натуральные числа L1, L2, …, LN, разделенные пробелом (1 ≤ Li ≤ 1000).
Выходные данные
Выходные данные находятся в файле output.txt, который в первой строке содержит максимальное количество песен C, которые предприниматель может записать на кассеты.

Пример
input.txt
3 2 4
1 4 1
output.txt
2

Вроде написал свое решение, но оно работает некорректно. К примеру на тесте:
8 4 6
4 2 4 2 6 6 4 2 (Выдает ответ 4, что является неверным)
А на примере :
8 4 6
4 2 4 2 5 5 4 2(тут Выдает уже ответ 7, что является верным)
Не могу понять что делаю не так, в случае когда длина песни равна объему кассеты.
Вот мой код:

Java
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
public class Solution {
     static BufferedReader in;
     static StringTokenizer st;
 
 
 static String next() throws IOException {
  if (st == null || !st.hasMoreTokens()) 
  {
      String line = in.readLine();
      if (line == null)
          return null;
      st = new StringTokenizer(line);
  }
  return st.nextToken();
}
 
 public static void main(String[] args) {
      try {
          boolean tack = false;
       in = new BufferedReader(new FileReader("input.txt"));
       PrintWriter out = new PrintWriter(new FileWriter("output.txt"));
       int n = Integer.parseInt(next());
       int m = Integer.parseInt(next());
       int d = Integer.parseInt(next());
       int[] l = new int[n];
       for (int i = 0; i < n; i++)
          l[i] = Integer.parseInt(next());
       
       int space = 0,next_i = 0,next_j=0,next_k=0;
       int[][][] mas = new int[n + 1][m + 1][d];
       
       for (int i = 0; i < n; i++) 
       {
          for (int j = 0; j < m; j++) 
          {
              for (int k = 0; k < d; k++) 
              {
                  space = l[i];
                  next_i = i + 1;
                  next_j = j;
                  next_k = k + space;
          
                  if (need_space > d)
                      continue;
          
                  if (next_k > d) 
                  {
                      next_j++;
                      next_k = space;
                  }
          
                  if (next_k == d) 
                  {
                      next_j++;
                      next_k = 0;
                  }
          
                  if (next_i > n || next_j > m || next_k >= d)
                      continue;
          
                  if (mas[next_i][next_j][next_k] < mas[i][j][k] + 1)
                      mas[next_i][next_j][next_k] = mas[i][j][k] + 1;
 
              }
          }
       }
       
       int res = 0;
       for (int i = 0; i < n + 1; i++)
          for (int j = 0; j < m + 1; j++)
              for (int k = 0; k < d; k++)
                  res = Math.max(res, mas[i][j][k]);
 
       out.println(res);
       out.close();
      } catch (IOException e) {
       
      }
    }
 
}

@Hyskills · 15.03.2016, 15:56 **[ТС]**

Сообщение от Dsasdf

хорошо, когда все условия пишутся сразу

Добавлено через 14 часов 2 минуты
Задача с сайта - http://www.e-olymp.com
Что не так:
1 Условие "задачи" писалось строго под один из численных методов в математике исключая все остальные решения введенными ограничениями. Т.е. если знаешь этот числ. метод - решишь, не знаешь - не решишь. Все сводится на это. А затем выкладывается как "задача для массового решения".
2 В условии умолчали, что "предприниматель" способен прослушать песню только один раз.
3 В рейтинге по потребляемым ресурсам побеждать всегда будет только С и С++, остальные языки несправедливо равняются к ним, потому, что многие языки изначально, ввиду специфики своей работы, потребляют больше, чем вышесказанные - С и С++.

Как решается:
Раскладываются в ряд все кассеты по минутах. Берется песня и делается вывод можно ли ее записать в одну минуту, две, три и т.д.
1 Составляется таблица значений, где число столбцов равно общему числу минут доступных для записи, а число строк равно числу песен.+1+1 - для удобства
2 Если песню можно записать в выделенное время, то, каждый раз, ищется максимум накрест из соседней вверх ячейки и левой, с добавлением единицы к значению левой ячейки. Позиция левой ячейки считается так: верхняя ячейка минус длинна текущей песни, получается верхняя ячейка сдвинутая влево. Результат записывается в текущую ячейку.
3 Если - нет, ищется максимум из накрест лежащих ячеек, одной влево, другой вверх ячеек, без добавления единицы.
4 Повторяется столько раз, сколько песен в таблице, пока не заполнится вся таблица. Согласно доказательству, результат будет всегда в крайней нижней правой ячейке таблицы, т.е. чтобы получить результат надо вычислить полностью всю таблицу.
Вот пример:

Пример решения:

Java
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
37
import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        int N = 0, M = 0, D = 0;
        int[] musicLength = null;
        int[][] table = null;
 
        try (Scanner sc = new Scanner(new File("input.txt"))) {
 
            M = sc.nextInt();
            D = sc.nextInt();
            N = sc.nextInt();
            musicLength = new int[N + 1];
            table = new int[N + 1][M * D + 1];
 
            for (int i = 1; i <= N; i++)
                musicLength[i] = sc.nextInt();
        } catch (FileNotFoundException ex) {
        }
 
        for (int i = 1; i <= N; i++)
            for (int j = 1, val = 1; j <= M * D; j++, val = (val + 1 > D) ? 1 : val + 1)
                if (musicLength[i] <= val)
                    table[i][j] = Math.max(table[i - 1][j], table[i - 1][j - musicLength[i]] + 1);
                else
                    table[i][j] = Math.max(table[i][j - 1], table[i - 1][j]);
 
        try (PrintWriter pw = new PrintWriter(new File("output.txt"))) {
            pw.println(table[N][M * D]);
        } catch (FileNotFoundException ex) {
        }
 
    }
}

Сообщение от Dsasdf

Согласно доказательству, результат будет всегда в крайней нижней правой ячейке таблицы, т.е. чтобы получить результат надо вычислить полностью всю таблицу.

О каком док-ве идет речь?
Можно сказать я понял как вы заполняете таблицу и убедился в том что это работает, но не понятно на чем основано такое заполнение таблицы.

@Aviz__ · 28.03.2016, 15:50

Придумал свой алгоритм этой задачки. Моделировал "в лоб" по ООП. Проект в IntelliJ прикрепляю.
Алгоритм работает так:
Первая песня записывается в первую же кассету по умолчанию. Если вторая песня не влезает в первую кассету, то она отбрасывается. Если третья песня не влезает, то меняется кассета.
Так же сделал метод из проги данной Dsasdf и сравниваю со своим результатом. Мой проигрывает и довольно существенно.
Результат работы программы:

Bash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Этот алгоритм может записать 12 песен, из 20
будет не использовано 5 единиц времени, из 56 имеющихся на 8 кассетах
Лучший теоритический алгоритм может записать: 16 песен
 
Хотите изменить "порядок" песен? y
y
Этот алгоритм может записать 11 песен, из 20
будет не использовано 12 единиц времени, из 56 имеющихся на 8 кассетах
Лучший теоритический алгоритм может записать: 15 песен
Продолжить ? y
y
Этот алгоритм может записать 12 песен, из 20
будет не использовано 2 единиц времени, из 56 имеющихся на 8 кассетах
Лучший теоритический алгоритм может записать: 16 песен
Продолжить ? y

Ну и генератор input.txt

Java
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
37
38
39
40
41
42
43
44
package Workout;
 
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Random;
 
/** */
public class MakerInputFile {
    private static final int COUNT_CASETTES = 8;
    private static final int CASETTE_VOLUME = 7;
    private static final int UPER_LIMIT_RANDOM_TRACK_VOLUME = 6;
    private static final int LOWER_LIMIT_RANDOM_TRACK_VOLUME = 2;
    private static final int COUNT_MUSIC_TRACKS = 20;
 
    private static void makeInputFile(String fileContentForStore) throws FileNotFoundException {
        PrintWriter writer = new PrintWriter("input.txt");
        writer.print(fileContentForStore);
        writer.close();
    }
 
    public static void main(String[] args) throws FileNotFoundException {
        Random randomNumbers = new Random();
        int counter = 0;
        int summaRandomNum = 0;
        String fileContent = "";
 
        while (counter < COUNT_MUSIC_TRACKS) {
            int tmp = randomNumbers.nextInt(UPER_LIMIT_RANDOM_TRACK_VOLUME);
            if (tmp >= LOWER_LIMIT_RANDOM_TRACK_VOLUME) {
                fileContent += String.format("%s ", new String(String.valueOf(tmp)));
                summaRandomNum += tmp;
                counter++;
            }
        }
        fileContent = new String(String.valueOf(COUNT_CASETTES)) + "\r\n" + new String(String.valueOf(CASETTE_VOLUME)) + "\r\n"
                + new String(String.valueOf(COUNT_MUSIC_TRACKS)) + "\r\n" + fileContent;
        try {
            makeInputFile(fileContent);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        System.out.println("\n" + summaRandomNum);
    }
}

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .