Problema de la mochila simple

El problema de la mochila simple, també cridat problema de la mochila supercreciente, és un tipo de problema de la mochila (problema NP-complet) al que li apliquen una série de condicions que fan que puga ser plantejat com un problema de la suma de subconjunts (problema NP-complet) que, si té solució, esta serà única.

Este tipo de problemes té importants aplicacions en el món de la criptografia

Definició

Donats: Un conjunt de m número entero positius S={S₁, S₂, ..., S_m}, ordenats de menor a major, a on la seqüència dels elements complixen la condició de que l'element i-ésimo és major que la suma dels anteriors elements (és una seqüència supercreciente). Matemàticament

$w_i>\sum _{j=1}^{i-1}{w}_j\mathrm{\forall }i$

Un valor T que és el resultat d'alguna de les possibles sumes d'eixos elements,

Es deu trobar S'={S_a, S_b, ..., S_j}, sent S' el subconjunt de S que la seua sumixca siga igual al valor T.

Resolució

La solució a este tipo de mochila és molt fàcil degut a que la seqüència S és una seqüència supercreciente:

Es recorren els elements de la mochila de major a menor comprovant si dit valor és menor que T. Si és major, eixe valor no estarà en la suma i per tant en la posició corresponent del vector solució x_i hi haurà un 0. En cas contrari tindrà un 1 i es continuarà la resolució en els restants elements de la mochila per al problema T-S_j

Per a este tipo de problemes, en el cas de que existixca la solució, esta serà única.

Bibliografia

Jorge Ramió Aguirre,"Aplicacions criptográficas: llibre guia de l'assignatura seguritat informàtica". Universitat Politècnica, Escola Universitària d'Informàtica. Giner 1998.