Доброго времени суток!

У меня возникла задача, в ходе решения которой я столкнулся с некоторой проблемой, которую необходимо решить.

Проблема такая — пусть имеется несколько (t) переменных, которые могут принимать значения от нуля до nt, где nt для каждой переменной своя. Необходимо найти все комбинации этих переменных, причем такие, чтобы их сумма была равна некоторому наперед заданному числу m.

Пример. 3 переменные a, b, c, a=0..4, b=0..5, c=0..2, m=3
Тогда
a b c
-----
0 1 2
0 2 1
0 3 0
1 0 2
1 1 1
1 2 0
2 0 1
2 1 0
3 0 0

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

Если кто-нибудь сталкивался с подобной проблемой, пожалуйста, напишите решение или дайте ссылку на него.

Заранее благодарен.

Здравствуйте, Grey2002, Вы писали:

G>Проблема такая — пусть имеется несколько (t) переменных, которые могут принимать значения от нуля до nt, где nt для каждой переменной своя. Необходимо найти все комбинации этих переменных, причем такие, чтобы их сумма была равна некоторому наперед заданному числу m.

public class Sum {
    final static int nt[] = {4, 5, 2};
    final static int m = 3;
    static int sum  = 0;
    static int p[];

    public static void gen(int k, int sum, int m) {
        if (k == nt.length-1) {
            p[k] = m;
            for (int i = 0; i < p.length; i++) {
                System.out.print(p[i] + " ");
            }
            System.out.println();
        } else {
            for (int i = Math.max(m-sum+nt[k], 0); i <= Math.min(m, nt[k]); i++) {
                p[k] = i;
                gen(k+1, sum-nt[k], m-i);
            }
        }
    }

    public static void main(String[] args) {
        if (nt.length > 0) {
            p = new int[nt.length];
            for (int i = 0; i < nt.length; i++) sum += nt[i];
            gen(0, sum, m);
        }
    }
}

0 1 2 
0 2 1 
0 3 0 
1 0 2 
1 1 1 
1 2 0 
2 0 1 
2 1 0 
3 0 0

Здравствуйте, Grey2002, Вы писали:

G>Проблема такая — пусть имеется несколько (t) переменных, которые могут принимать значения от нуля до nt, где nt для каждой переменной своя. Необходимо найти все комбинации этих переменных, причем такие, чтобы их сумма была равна некоторому наперед заданному числу m.

Обобщение задачки "генератор счастливых трамвайных билетов".
Решается следующим образом.

С твоего позволения, переименую переменные на свой вкус.
Есть n переменных x[1]..x[n], каждая из которых принимает значения x[k] in [ xmin[k]..xmax[k] ]
(В твоём случае, min[k] = 0).

Нужно перебрать комбинации такие, что sum(k=1..n) x[k] = S.

Введём функции
Min[i] = sum(k=i..n) xmin[k]
Max[i] = sum(k=i..n) xmax[k]

Очевидно, что решение задачи существует только в том случае, если S in [ Min[1]..Max[1] ]

Пусть мы нашли и зафиксировали первые k-1 переменных x[1]..x[k-1]. Их сумма составила X.
Это значит, что оставшиеся x[k]..x[n] должны дать сумму C = S-X.
На неё действует такое же ограничение: C in [ Min[k]..Max[k] ]
Допустим, что это истинно, то есть, фиксируя переменные, мы не нарушили этого условия.
Попробуем выяснить, какое ограничение действует на x[k]

C-x[k] in [ Min[k+1]..Max[k+1] ]
Min[k+1] <= C-x[k] <= Max[k+1]
Min[k+1]-C <= -x[k] <= Max[k+1]-C

C-Max[k+1] <= x[k] <= C-Min[x+1]
ну и кроме того, действует требование xmin[k] <= x[k] <= xmax[k]
то есть
max( min[k], C-Max[k+1] ) <= x[k] <= min( max[k], C-Min[k+1] )

Можно домыслить, что Min[n+1]=Max[n+1]=0, то есть для k=n это неравенство будет выглядеть как
C <= x[n] <= C
x[n] = C

---

Итого,
1) находим значения Min[], Max[]
2) инициализируем массив x[]

C=S
для k от 1 до n
  x[k] = max( xmin[k], C-Max[k+1] )
  C -= x[k]

3) выводим массив x[]
4) переходим к следующему значению: начиная с x[n], пытаемся инкрементировать (ограничивая себя сверху); если потолок исчерпан, то переходим к предыдущей переменной

C = 0
k = n
цикл
  если x[k] < min( xmax[k], C-Max[k+1] )
    x[k]++
    C -= x[k]
    для k' от k+1 до n : выполнить инициализацию как в (2)
    выйти из цикла
  иначе
    C += x[k]
    k--
    если k=0
      закончить работу: мы перебрали все комбинации
    иначе
      повторить попытку