Минимальное количество массивов

@balalexv · Регистрация: 07.07.2014

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

Приветствую!

Допустим, есть массив натуральных чисел длиной N, таких, что все они меньше некоторого X. Например, { 1, 1, 3, 3, 2, 1, 3, 1 } (N = 8, X = 4}. Требуется найти такой набор массивов натуральных чисел, которые вместе содержат в себе все числа из исходного массива, сумма чисел в каждом из них меньше или равна X, а их количество - минимально.

Для случаев, когда X <= 4, удалось придумать некоторый костыль, но как обобщить его на общий случай не получается (например, если мы говорим про X = 4, то тройки могут "склеиться" только с единичками, из двоек будут получаться отличные четверки, а из оставшихся единиц и, опционально, двойки - что угодно).

p.s. не откажусь от любого варианта, но если возможно - C# предпочтителен

.

@ProgJ · 24.10.2015, 11:40

Да, при больших X, например 15, лучше взять разложение 7+5+3, чем 7+7+1, а определять приоритет можно по последнему (минимальному) числу

@balalexv · 26.10.2015, 12:20 **[ТС]**

Проблема в том, что я не уверен в том, что такой подход универсален (в том смысле, что он будет давать однозначно минимальное значение). Ну и, если честно, код "в общем случае" написать у меня не получается.

@Shamil1 · 26.10.2015, 15:04

В общем случае - только перебор.

@balalexv 0 / 0 / 0 Регистрация: 07.07.2014 Сообщений: 14
		1
	Минимальное количество массивов 23.10.2015, 14:18. Показов 421. Ответов 3 Метки нет (Все метки) Приветствую! Допустим, есть массив натуральных чисел длиной N, таких, что все они меньше некоторого X. Например, { 1, 1, 3, 3, 2, 1, 3, 1 } (N = 8, X = 4}. Требуется найти такой набор массивов натуральных чисел, которые вместе содержат в себе все числа из исходного массива, сумма чисел в каждом из них меньше или равна X, а их количество - минимально. Для случаев, когда X <= 4, удалось придумать некоторый костыль, но как обобщить его на общий случай не получается (например, если мы говорим про X = 4, то тройки могут "склеиться" только с единичками, из двоек будут получаться отличные четверки, а из оставшихся единиц и, опционально, двойки - что угодно). p.s. не откажусь от любого варианта, но если возможно - C# предпочтителен . 0

@ProgJ 90 / 87 / 11 Регистрация: 20.11.2008 Сообщений: 724
	24.10.2015, 11:40	2
	Да, при больших X, например 15, лучше взять разложение 7+5+3, чем 7+7+1, а определять приоритет можно по последнему (минимальному) числу 0

@balalexv 0 / 0 / 0 Регистрация: 07.07.2014 Сообщений: 14
	26.10.2015, 12:20 [ТС]	3
	Проблема в том, что я не уверен в том, что такой подход универсален (в том смысле, что он будет давать однозначно минимальное значение). Ну и, если честно, код "в общем случае" написать у меня не получается. 0

@Shamil1 Модератор 3070 / 2218 / 461 Регистрация: 26.03.2015 Сообщений: 8,562
	26.10.2015, 15:04	4
	В общем случае - только перебор. 0

Опции темы