variación interesante al problema de la suma de subconjuntos

Question

Una variación interesante de la suma de subconjuntos problema se presentó a mí por un amigo del trabajo:

Dado un conjunto S de números enteros positivos, de tamaño n, y los números enteros a y K, ¿existe un subconjunto R (del conjunto S) que contiene exactamente unos elementos , cuya suma es igual a K?

Afirma que esto se puede hacer con el tiempo la complejidad O (NKA), que era incapaz de llegar a un algoritmo de programación dinámica que logra este tiempo de funcionamiento. ¿Se puede hacer?

Answer 1

Se puede hacer si k y son lo suficientemente pequeños, de manera que podamos declarar una matriz

bool found[a][k]

Se podría iterar sobre cada valor de S y iterar sobre todos los estados de la encontrados array para obtener un nuevo estado.

Digamos, por los índices de a = 1 y k = 7, y el valor actual de S siendo 7,

si se encuentra [1] [7] es cierto, entonces también se puede estar seguro de la que se encuentra [2] [14] también es cierto.

Cuando termina la iteración, todo lo que tiene que hacer es comprobar que [a] [k] es verdad o no.

Answer 2

Sea S = {s1, \ ldots, sn}

Sea P (j, k, a) si y sólo si es verdad que es posible encontrar una serie de elementos en s1, \ ldots, sj que suma hasta K.

A continuación, P (j, K, a) = P (j-1, K-sj, a-1) o P (j, K, A) (se necesita ya sea sj o no se necesita).

El algoritmo consiste entonces de llenar tabla 3-D de dimensión n por K + 1 por un + 1. Cada entrada de toma constante de tiempo de llenar, por lo tanto el tiempo (y espacio) la complejidad es O (NKA)