El problema de la mochila

Estoy trabajando en un algoritmo de los llamados NP-Completos
En particular se llama "el problema de la mochila" el cual consiste en lo
siguiente:
Sean n objetos y una mochila. Para que = 1,2,..., n, el objeto que tiene un peso positivo porque y un valor positivo vk.
La mochila puede llevar un peso total que no sobrepase P.
Se pretende llenar la mochila de forma que el valor de los objetos transportados sea máximo.
Supondremos que los objetos no se pueden fraccionar.
Expresaremos la solución mediante un vector por de valores 0 ó 1.
Para k = 1,2,...,n, si xk = 1 entonces el objeto k
debe estar en la mochila; si xk = 0 entonces el objeto k no se selecciona.
Matemáticamente, el problema lo podemos enunciar de la siguiente forma:
Encontrar un vector por de n elementos del conjunto {0,1} de forma que:
La sumatoria desde k=1 hasta n de Xk*Vk sea máximo con la restricción:
La sumatoria desde k=1 hasta n de Xk*Pk < P
(Xk quiere decir Vector X subindice k)
He encontardo 3 algoritmos los cuales he implementado en C++ y C++.NET, sin embargo la complejidad
de estos algoritmos es muy alta, para una corrida con 42 elementos tarda horas, lo cual hace
que no lo pueda utilizar. De donde saque esta información (http://www.dlsi.ua.es/asignaturas/pm/prac3-2000.pdf)
Se hacía referencia a un cuarto algoritmo
en donde se mejora la complejidad sin embargo asume que los objetos se pueden fraccionar lo cual no
es mi caso.
Me pregunto si alguien me puede ayudar a encontrar un algoritmo que resuelva el problema en un
tiempo mucho menor.
A continuación describo el programa en C++ del primer algoritmos, los demás no los pude adjuntar por
problemas de espacio, son muy similares y se pueden ver en http://www.dlsi.ua.es/asignaturas/pm/prac3-2000.pdf
Forma de llamarlo:
int v[43];
int p[43];
int x[43];
int x_mejor[43];
int v_mejor;
int peso;
int n;
v_mejor = -1;
n=42
peso=610
v[0] = 0;//el primer elemento de la matriz no se utiliza
v[1] = 1;
v[2] = 1;
v[3] = 1;
v[4] = 1;
v[5] = 1;
v[6] = 1;
v[7] = 90;
v[8] = 90;
v[9] = 80;
..
..
v[42]=40;
p[0] = 0;//el primer elemento de la matriz no se utiliza
p[1] = 1;
p[2] = 1;
p[3] = 1;
p[4] = 1;
p[5] = 1;
p[6] = 1;
p[7] = 90;
p[8] = 90;
p[9] = 80;
..
..
p[42]=40;
Mochila(v,p,peso,42,1,x,x_mejor,&v_mejor);
Algoritmo 1.
int Mochila(int v[],int p[],int peso,int n,int k, int x[],int x_mejor[],int *v_mejor)
{
int local_peso;
int local_valor;
int i;
x[k] = -1;
while (x[k] < 1)
{
x[k] = x[k] + 1;
local_peso = 0;
for (i=1;i<=k;i++){
local_peso = local_peso + (x * p);
}
if (local_peso <= peso)
{
if (k == n)
{
local_valor = 0;
for (i=1; i<=k;i++){
local_valor = local_valor + (x * v);
}
if (local_valor > *v_mejor)
{
for (i=1;i<=k;i++){
x_mejor = x;
}
*v_mejor = local_valor;
}
}
else if (k < n)
{
Mochila (v, p, peso, n, k + 1, x, x_mejor, v_mejor);
}
}
}
return 0;
}