Линейное неравенство с целыми неотрицательными коэфф-тами

[madschumacher]

Добрый день.

Прошу прощения за беспокойства.
Имеется функция
$E = \sum_{i=1}^{N_a} n_{i} A_i + \sum_{j=1}^{N_b} m_{j} B_j$ с целыми $n_i, m_j \geq 0$, $A_i \leq A_{i+1}$, $B_j \leq B_{j+1}$ и условиями $ \begin{cases} \sum_i n_i = N \\ \sum_j m_j = M \end{cases} $
Я хочу перебрать все решения неравенства
$E - E_{\min} \leq \Delta E$
при заданном $\Delta E$.
Пытался решить эту проблему методом МК, генерируя разные перестановки минимального набора $n_i,m_j$, но так получается куча решений, который мне не нужны. Можно ли как-то эту задачу поумнее поставить/более адекватно решить?

[vpb]

madschumacher в сообщении #1426968 писал(а):

Пытался решить эту проблему методом МК, генерируя разные перестановки минимального набора $n_i,m_j$, но так получается куча решений, который мне не нужны.

Мне в этой фразе не понятно ни одного слова. Можете написать подробнее, с каким-нибудь маленьким примером ?

Еще вопрос для контроля, что я правильно постановку задачи понимаю. Верно ли, что $E_{\min}=NA_1+MB_1$ ?

[madschumacher]

vpb в сообщении #1426974 писал(а):

Еще вопрос для контроля, что я правильно постановку задачи понимаю. Верно ли, что $E_{\min}=NA_1+MB_1$ ?

Спасибо большое, хороший вопрос, показывающий, что я опять намудрил с упрощением, в частности забыв важное условие.
Больше я так делать не буду, поэтому напишу физическую задачу, которая, надеюсь, будет иметь понятную постановку.

Итак, имеется система электронов из $N$ электронов, из них $N_\uparrow$ имеют спин "вверх", а $N_\downarrow$ -- "вниз" ($N = N_\uparrow + N_\downarrow$). Первые могут сидеть в ячейках с энергиями $\{ \varepsilon_i^\uparrow \}_{i=1}^{M_\uparrow}$, а другие в ячейках с энергиями $\{ \varepsilon_j^\uparrow \}_{j=1}^{M_\downarrow}$, причём для упрощения энергии ячеек можем считать упорядоченными ($\varepsilon_i \leq \varepsilon_{i+1}$). В каждой ячейке может сидеть только один электрон, перестановка электронов не меняет состояния. Таким образом полная энергия состояния даётся формулой
$E = \sum_{i=1}^{M_\uparrow} n_i^\uparrow \varepsilon_i^\uparrow + \sum_{j=1}^{M_\downarrow} n_j^\downarrow \varepsilon_i^\downarrow$,
где числа заселённости ячеек $n$ могут принимать значения 0 и 1, соответственно, $\sum_{i=1}^{M_\uparrow} n_i^\uparrow = N_\uparrow$ и $ \sum_{j=1}^{M_\downarrow} n_j^\downarrow = N_\downarrow$.
Минимальной является энергия $E_{\min}$, когда $n_1^q = n_2^q = \ldots = n_{N_q}^q = 1$ и $n_{N_q+1}^q = \ldots = n_{M_q}^q$ ($q = \uparrow, \downarrow$), т.е. заняты только ячейки с наименьшими энергиями.

Похожую задачу (но с непрерывными заселённостями) я уже постил раньше (https://dxdy.ru/topic131010.html).
Соответственно, вопрос состоит в том, чтобы найти все возбуждённые состояния (т.е. состояния с энергией больше или равной минимальной) с энергией меньше заданной разницы $\Delta E$ ($E - E_{\min} \leq \Delta E$).

Перебор всех перестановок, к сожалению, не работает, т.к. ячеек может быть достаточно много. Поэтому я находил ячейку, максимально достижимую с последней занятой, ограничивался только ячейками ниже неё по энергии, и пытался гнать Монте-Карло, перебирая случайные перестановки. К сожалению, лишних (не удовлетворяющих неравенству) состояний всё ещё слишком много и они забивают всю статистику.

[mihiv]

Все же нужны еще некоторые подробности. Конечно или бесконечно число уровней? Как соотносятся энергии $\varepsilon _i $ и $\Delta E$?
Например, приведенному условию не противоречит вариант: число уровней бесконечно и $\varepsilon _1=\varepsilon _2=\cdots =\varepsilon _i=\cdots, \varepsilon _1N<\Delta E$. В этом случае число решений неравенства может быть бесконечно.

[DeBill]

madschumacher в сообщении #1426982 писал(а):

Поэтому я находил ячейку, максимально достижимую с последней занятой, ограничивался только ячейками ниже неё по энергии, и пытался гнать Монте-Карло

Зачем сразу МонтеКарло? Ведь получается такая же задача - так рекурсивно ее и решать...
Т.е., план такой :
1. находим макимально возможный уровень для "вверх",
2. (цикл пошел) суем туда электрон, и решаем такую же задачу для оставшихся (электронов и остатка энергии);
перекладываем главный электрон на меньший уровень, и решаем такую же задачу;
и т.д... (только надо будет запретить электроны класть выше главного)
3. (внутренний цикл пошел) внешний цикл закончит работу, когда все электроны "вверх" займут какие-то позиции. Теперь то же делаем с теми, кто "вверх"....

(Оффтоп)

А вот если уровни - просто степени двойки, то количество комбинаций можно найти явно. Скажем, если есть только "вверх", то кол-во комбинаций считается...