¿Cómo encontrar todas las combinaciones que sumn como máximo una constante?

Sea P=[P1, P2, ..., Pk] como k enteros positivos y sea T un entero positivo. Me gustaría generar todas las combinaciones que sumen como máximo T Es decir, sum(x[i] * P[i] for i in 1:k) <= T donde x[i] = 1 si se elige i en la combinación.

Ejemplo.

Sean P=[1, 2, 3] y T=4 . Las combinaciones deben ser:

 1 2 3 1, 2 1, 3 2, 3 

Entonces, solo la combinación 1, 2, 3 no puede estar allí porque 1 + 1 + 3 = 5 > 4 .

Pensé en generar todas las combinaciones primero y luego comenzar a verificar la sum(x[i] * P[i] for i in 1:k) <= T la restricción sum(x[i] * P[i] for i in 1:k) <= T Pero este enfoque podría llevar más tiempo que otros enfoques inteligentes. ¿Cómo podemos generar tales combinaciones?

NÓTESE BIEN. Si conoce alguna función en Python o Matlab que pueda usarse para generar tales combinaciones, puede proporcionarla.

Gracias.

Esto es como el problema de la sum de subconjuntos (mencionado en los comentarios), excepto que se trata de encontrar números que sumen igual a un objective. Desea encontrar números que sumen un total menor o igual que el objective.

No obstante, se puede utilizar un enfoque similar con la progtwigción dinámica:

 def subset_sum(vals, target=0): sums = {0: [()]} # key=sum, value=list of subsets for the sum if target in sums: yield from sums[target] # annoying base case for val in vals: items = sums.items() # don't change dict size during iteration sums = dict(items) for prev_sum, prev_subsets in items: sum_ = prev_sum + val subsets = [s + (val,) for s in prev_subsets] sums[sum_] = sums.get(sum_, []) + subsets if sum_ <= target: yield from subsets 

Manifestación:

 >>> for subset in subset_sum([1, 2, 3], target=4): ... print(*subset, sep='+') ... 1 2 1+2 3 1+3