- C ++
- управління завданнями
- алгоритми
Доброго дня.
Зіткнувся з завданням розподілу N елементів різної розмірності в M контейнерів різної розмірності. Повністю умова формулюється ось так:
В якості вхідних даних є:
M - число контейнерів, M чисел A1. An, що відповідає місткості контейнерів (в елементах).
N - число елементів, N чисел B1. Bn, відповідно розміри цих елементів.
Завдання полягає в тому, щоб видати оптимальний розподіл елементів по контейнерах в такому варіанті:
Вивести N чисел, де j-те число повинне позначати номер контейнера, в який ми кладемо j-тий елемент.
Наприклад:
4 контейнери, місткістю
11 7 4 3
5 елементів, розмірністю
6 3 2 4 5
Висновок (один з можливих):
1 2 4 2 1
На жаль в алгоритміці і NP-завданнях не сильний, і поки своїх ідей на цю тему не дуже багато. Думав про сортування від більшого до меншого і простому перебору на заповнення - тобто спробувати якомога оптимальніше використовувати найбільший контейнер, потім другий за ним і т.д. але в цьому випадку у мене постає проблема збереження початкової індексації (порядку).
Підкажіть, будь ласка, або статті на почуття на цю тему, або відповідний алгоритм. Заздалегідь дякую)