Múltiples códigos de solución para el problema de la mochila 0-1 (programación dinámica, método codicioso, método de retroceso, método de bifurcación y enlace)
1. Programación dinámica para solucionar el problema de la mochila 0-1
/************************ ***** ********************************************** **/
/* Problema de mochila 0-1:
/* Dados n artículos y una mochila
/* El peso del artículo i es wi, y su valor es vi
/* La capacidad de la mochila es c
/* ¿Cómo se deben seleccionar los artículos cargados en la mochila para que se cargue el número total de artículos? la mochila
/*¿El mayor valor?
/* Nota: Al seleccionar artículos para poner en la mochila, solo hay dos opciones para el artículo i,
/* Es decir, ponerlo en la mochila o no. El elemento i no se puede cargar varias veces, ni
/* solo se puede cargar una parte del elemento i.
/*
/* 1. Descripción formal del problema de la mochila 0-1:
/* Dado c>0, wi>0, vi > 0, 0<=i<=n, se requiere encontrar un vector de n elementos
/* 0-1 (x1, x2, ..., xn), tal que:
/* max sum_{i=1 to n} (vi*xi), y satisface las siguientes restricciones:
/* (1) sum_{i=1 to n} (wi* xi) <= c
/* (2) xi∈{0, 1}, 1<=i<=n
/*
/* 2. Solución 0-1 al problema de la mochila
/* El problema de la mochila 0-1 tiene propiedades de subestructura óptimas y propiedades de superposición de subproblemas, y es adecuado para solución
/* usando dinámica métodos de programación
/*
/* 2.1 Propiedades óptimas de la subestructura
/* Supongamos que (y1, y2,...,yn) es un 0- dado. 1 problema de mochila Una solución óptima debe ser
/* Conclusión, (y2, y3,...,yn) es una solución óptima para el siguiente subproblema:
/* suma máxima_{i=2 a n} (vi*xi)
/* (1) suma_{i=2 a n} (wi*xi) <= c - w1*y1
/* (2) xi∈{0, 1}, 2<=i<=n
/* Porque si no, entonces existe una solución óptima para este subproblema (z2, z3,..,zn),
/* y (y2,y3,...,yn) no es su solución óptima.
Luego están:
/* sum_{i=2 to n} (vi*zi) > sum_{i=2 to n} (vi*yi)
/* Y , w1*y1 + sum_{i=2 an} (wi*zi) <= c
/* Además:
/* v1*y1 + sum_{i=2 a n} (vi*zi) > suma_{i=1 a n} (vi*yi)
/* w1*y1 + suma_{i=2 a n} (wi*zi) <= c
/* Esto muestra que (y1, z2, z3,...zn) es una mejor solución al problema de mochila 0-1 dado, entonces
/* muestra ( y1, y2,...,yn) no es la solución óptima al problema y contradice la premisa, por lo que se establece la propiedad de subestructura óptima
/*.
/*
/* 2.2 Propiedades superpuestas de los subproblemas
/* Supongamos que el subproblema P(i,j) del problema de mochila 0-1 dado es ：
/* suma máxima_{k=i a n} (vk*xk)
/* (1) suma_{k=i a n} (wk*xk) < = j
/* (2) xk∈{0, 1}, i<=k<=n
/* El problema P(i,j) es una mochila con una capacidad de j , subproblema cuando los elementos opcionales son i, i+1,...,n
/* Sea m(i,j) el valor óptimo del subproblema P(i ,j), que es el valor total máximo. Luego, de acuerdo con las propiedades óptimas de la subestructura
/*, se puede establecer la fórmula recursiva de m(i,j):
/* a.
/* p>
/* //La capacidad de la mochila es j, y los artículos opcionales son solo n si la capacidad de la mochila j es mayor que el peso del artículo n
<. p>/* // El peso se carga directamente; de lo contrario, no se puede cargar./* m(n,j) = vn, j>=wn
/* m(n,j) = 0, 0<=j /* b. Fórmula recursiva m(i,j) /* //La capacidad de la mochila es j y los elementos opcionales son i,i+1,...,n /* //Si la capacidad de la mochila j /* m(i,j) = m(i+1 ,j), 0<=j /* //Si j>=wi, elige entre no cargar el elemento i y cargar el elemento i /* No cargar El óptimo valor del artículo i: m(i+1,j) /* El valor óptimo del artículo cargado i: m(i+1, j-wi) + vi / * Entonces: /* m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j>= wi /* /********************************* *** ***************************************/ #definir máximo (a,b) (((a) > (b))? (a): (b)) #define min(a,b) (((a) < (b))? (a) : (b)) plantilla void Knapsack(Type* v, int *w, int c, int n, Type **m) { //Condición inicial recursiva int jMax = min(w[n] - 1, c for (); int j=0; j<=jMax; j++) { m[n][j] = 0 } para (j= w; [n]; j<=c; j++) { m[n][j] = v[n] } // yo; de 2 a n-1, respectivamente para j>=wi y 0<=j para (int i=n-1; i>1; i- -) { jMax = min(w[i] - 1, c for (int j=0; j<=jMax; j++) { m[i][j] = m[i+1][j]; } para (j=w[i]; j<=c; j++) { m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]); /p> } } m[1][c] = m[2][c] if (c >=; w[1]) { metro [1][c] = máx(m[1][c], m[2][c-w[1]]+v[1]); plantilla void TraceBack(Tipo **m, int *w, int c, int n, int* x) { for (int i=1; i if(m[i][c] == m[i+1][c]) x[ i] = 0; más { x[i] = 1 c -= w[i]; } } x[n] = (m[n][c])? int main(int argc, char* argv[]) { int n = 5 int w[6] = {-1, 2; , 2, 6, 5, 4}; int v[6] = {-1, 6, 3, 5, 4, 6}; int **ppm = nuevo int*[n+1]; for (int i=0; i ppm[i] = nuevo int[c+1]; } int x[6]; , c, n, ppm); TraceBack devuelve } <; /p> 2. Algoritmo codicioso para resolver el problema de la mochila 0-1 1. La idea básica del método codicioso: ——Comience desde una inicial. solución del problema y abordarlo gradualmente. El objetivo dado es obtener una mejor solución lo más rápido posible. Cuando se alcanza un determinado paso en un algoritmo y no se puede avanzar más, el algoritmo se detiene. Hay problemas con este algoritmo: 1). No hay garantía de que la solución final obtenida sea la mejor. 2). se utiliza para encontrar la solución máxima o mínima del problema; 3). Solo puede encontrar el rango de soluciones factibles que satisfacen ciertas restricciones. El proceso de implementación de este algoritmo: Comienza desde una determinada solución inicial al problema mientras se puede dar un paso adelante hacia el objetivo general dado Encuentre un elemento de solución de una solución factible Combine todos los elementos de la solución en una solución factible del problema 2. p>1 ).[Problema de la mochila] Hay una mochila con una capacidad de M=150. Hay 7 artículos y los artículos se pueden dividir en cualquier tamaño. Se requiere maximizar el valor total de los artículos empaquetados en la mochila tanto como sea posible, pero no puede exceder la capacidad total. Artículo A B C D E F G Peso 35 30 60 50 40 10 25 Valor 10 40 30 50 35 40 30 Análisis: p> Función objetivo: ∑pimax La restricción es que el peso total de los artículos cargados no exceda la capacidad de la mochila: ∑wi<=M( M=150) （ 1) Según la estrategia codiciosa, cada vez que eliges el artículo con el valor más alto y lo guardas en tu mochila, ¿el resultado es el mejor? (2) ¿Se puede obtener la solución óptima seleccionando cada vez los elementos que ocupan el menor espacio? (3) Seleccionar el artículo con mayor valor por unidad de capacidad cada vez se convierte en la estrategia para resolver este problema. #include #define max 100 //Número máximo de elementos void sort (int n,float a[max],float b[max]) //Ordenar por densidad de valores { int j,h,k ; flotante t1,t2,t3,c[max]; for(k=1;k<=n;k++) c[k ] =a[k]/b[k]; for(h=1;h for(j=1;j<=n-h;j++ ) if(c[j] {t1=a[j];a[j]=a[j+1];a [j+1]=t1; t2=b[j];b[j]=b[j+1];b[j+1]=t2; t3 =c[j];c[j]=c[j+1];c[j+1]=t3 } } {float c1 //c1 es el peso cargable restante de la mochila. int i; sort(n,v,w); //Los elementos se ordenan por densidad de valor c1=limitw; p>for( i=1;i<=n;i++) { if(w[i]>c1)break x[; i]=1 ; //Cuando x[i] es 1, el elemento i está en la solución c1=c1-w[i] } } p> void main() {int n,i,x[max] float v[max]; w[max],totalv=0,totalw =0,limitw; cout<<"Ingrese n y limitw:" cin>>n >>limitw; /p> for(i= 1;i<=n;i++) x[i]=0; //La tabla de selección de elementos se inicializa a 0 cout<<"Ingrese el valor de los elementos en secuencia: "< for(i=1;i<=n;i++) cin>>v [i]; cout<< endl; cout<<"Ingrese el peso de los artículos en secuencia:"< cin>>w[i]; cout< cout <<"la selección es:" for(i=1;i<=n;i++) { cout< if(x[i]==1) totalw=totalw+w[i] ]; } cout< cout<<"El número total de la mochila. El peso es: "< cout<<"El valor total de la mochila es: "< } 3. Algoritmo de retroceso para resolver el problema de la mochila 0-1 El problema de la mochila de 1,0 l es un problema de selección de subconjuntos Generalmente, el problema de la mochila 0-1 es un problema NP-difícil. El espacio de solución del problema de la mochila 0-1 se puede representar mediante un árbol de subconjuntos. El problema de la mochila 0-1 es muy similar al método de retroceso para el problema de carga. De manera similar, al buscar en el árbol del espacio de soluciones, siempre que su nodo secundario izquierdo sea un nodo factible, la búsqueda ingresará su. subárbol izquierdo cuando El subárbol derecho puede contenerlo. Ingrese la búsqueda del subárbol derecho solo cuando se encuentre la solución óptima. De lo contrario, sea r el valor total de los elementos restantes actuales. cuando cp+. Cuando r≤bestp, se puede podar el subárbol derecho. Una mejor manera de calcular el límite superior de la solución en el subárbol derecho es ordenar los elementos restantes según su valor de peso unitario, y luego Cargue elementos en secuencia hasta que no quepan, luego cargue parte del elemento para llenar la mochila. El valor obtenido es el límite superior de la solución en el subárbol derecho Para facilitar el cálculo del límite superior, primero puede ordenar los elementos según su valor de peso unitario, de mayor a menor, y luego simplemente examinar cada elemento en orden. Eso es Durante la implementación, el límite se utiliza para calcular el límite superior en el nodo actual. Al buscar en el árbol del espacio de solución, siempre que su nodo secundario izquierdo sea un nodo factible, la búsqueda ingresará al subárbol izquierdo y es posible. el subárbol correcto solo cuando se incluya la solución óptima se podará el subárbol correcto El método de retroceso es un algoritmo de búsqueda que es a la vez sistemático y ágil en el árbol del espacio de soluciones. En la estrategia de profundidad primero, la búsqueda en el árbol del espacio de soluciones comienza desde el nodo raíz. Cuando el algoritmo busca cualquier nodo del árbol del espacio de soluciones, siempre determina primero si el nodo definitivamente no contiene un problema. incluido, omita la búsqueda sistemática del subárbol enraizado en este nodo y retroceda hasta sus nodos ancestros capa por capa. De lo contrario, ingrese al subárbol y continúe buscando de acuerdo con la estrategia de búsqueda en profundidad cuando se utiliza el método de retroceso para encontrar todas las soluciones. El problema, se debe rastrear hasta la raíz y se han buscado todos los subárboles del nodo raíz antes de finalizar. Cuando se utiliza el método de retroceso para encontrar alguna solución al problema, solo es necesario buscarlo. con una solución. Este algoritmo que busca sistemáticamente la solución al problema primero en profundidad se llama método de retroceso, que es adecuado para resolver problemas con una gran cantidad de combinaciones. Marco: a. Espacio de solución del problema: al aplicar el método de retroceso para resolver un problema, primero se debe definir claramente el espacio de solución del problema. una solución (óptima) al problema. b. La idea básica del método de retroceso: después de determinar la estructura organizativa del espacio de la solución, el método de retroceso comienza desde el nodo inicial (nodo raíz) y busca en profundidad todo el espacio de la solución. -primera manera. Este nodo inicial se convierte en un nodo activo y también se convierte en el nodo de expansión actual. En el nodo de expansión actual, la búsqueda se mueve en profundidad hasta un nuevo nodo. Este nuevo nodo se convierte en un nuevo nodo activo y se convierte en el nodo de expansión actual. Si el nodo de expansión actual no puede moverse en la dirección de profundidad, el nodo de expansión actual se convierte en un nodo muerto. En otras palabras, este nodo ya no es un nudo vivo. En este momento, debe retroceder (retroceder) hasta el nodo de deslizamiento más cercano y convertir este nodo de deslizamiento en el nodo de expansión actual. El método de retroceso busca recursivamente en el espacio de la solución de esta manera hasta que se encuentra la solución requerida o no hay nodos activos en el espacio de la solución. 3. El uso del método de retroceso para resolver problemas generalmente incluye los siguientes tres pasos: a. p> b. Determine la estructura del espacio de solución que sea fácil de buscar; c. Busque en el espacio de solución primero en profundidad y utilice funciones de poda durante el proceso de búsqueda para evitar búsquedas no válidas. p> #include usando el espacio de nombres std; clase Knap { amigo int Knapsack(int p[],int w[], int c,int n ); público: void print() { for(int m=1;m <=n;m++) { cout< cout< }; privado: int Bound(int i); >void Backtrack(int i); int c;//Capacidad de la mochila int n; //Número de artículos int *w;// Matriz de peso del artículo int *p;//Matriz de valor del artículo int cw;//Peso actual int cp;//Valor actual int bestp;//Valor óptimo actual int *bestx;//Solución óptima actual int *x;//Solución actual }; int Knap::Bound(int i) { //Calcular límite superior int cleft=c- cw;//Capacidad restante int b=cp; //Cargar artículos en orden descendente del valor de peso unitario while(i<=n&&w[ i]<=hendidura) { hendidura-=w[i] b+=p[i]; i++; } //Llena la mochila if(i<=n) b+=p[i]/ w[i]*cleft; return b; } void Knap::Backtrack(int i) { if (i>n) { if(bestp { for( int j=1;j< =n;j++) mejorx[j]=x[j] mejorp=cp } p> return; } if(cw+w[i]<=c) //Buscar en el subárbol izquierdo { x[ i]=1; cw+=w[i]; cp+=p[i] Retroceder(i) +1); p> if(Bound(i+1)>bestp)//Buscar en el subárbol derecho { x[i]=0 Backtrack( i+1); } } clase Objeto { amigo int Mochila(int). p[],int w[],int c,int n); público: int operador<=(Objeto a)const { return (d>=a.d); } privado: int ID float d; ; }; int Mochila(int p[],int w[],int c,int n) { //Inicializar Knap::Backtrack int W=0; int P=0 int i=1; >Objeto *Q=nuevo Objeto[n]; for(i=1;i<=n;i++) { Q[i - 1].ID=i; Q[i-1].d=1.0*p[i]/w[i]; /p> W+=w[i]; } if(W<=c) return P;//Cargar todos los elementos //Ordenar por peso unitario del artículo float f; for( i=0;i for(int j=i;j { if(Q[i].d { f=Q[i].d Q[i].d=Q[j].d Q[ j] .d=f; } } Knap K; K.p = nuevo int[n+1]; p> K.w = nuevo int[n+1]; K.x = nuevo int[n+1]; K.bestx = nuevo int[n+ 1]; K.x[0]=0; K.bestx[0]=0 para( i=1;i<=n ;i++) { K.p[i]=p[Q[i-1].ID] K.w[i]=w[Q[i-1]. 1].ID]; } K.cp=0 K.cw=0 K.c=c; K.n=n; K.bestp=0; //Búsqueda de retroceso K.Backtrack( 1); K.print(); eliminar [] Q; eliminar [] K.w eliminar [] K.p; /p> return K.bestp; } void main() { int * p; /p> int * w; int c=0; int n=0; int i=0; char k; p> int n=0; p> cout<<"0-1 problema de mochila - método de retroceso"< while( k) { cout<<"Ingrese la capacidad de la mochila (c):"< cout<<"Por favor, introduzca el número de elementos (n):"< w=nuevo int[n+1] p[0]=0; [0]=0; cout<<"Ingrese el valor del elemento (p):"< cin> >p[i]; cout<<"Ingrese el peso del artículo (w):"< cin>>w[i]; cout<<"La solución óptima es (bestx):" < cout<< "El valor óptimo es (bestp):"< cout< cout<<"[ s] Reiniciar"< cout<<"[q] Salir"< } 4. Método de bifurcación y encuadernación para resolver el problema de la mochila 0-1 1. son N artículos y una mochila que puede contener M peso, y el peso de cada artículo I Para PESO, solo se pueden colocar todos los artículos o no. Resolver cómo colocar los artículos puede maximizar el beneficio total del artículos en la mochila. 2. Ideas de diseño y análisis: la selección de elementos forma un árbol de soluciones. El subárbol izquierdo indica que no se está cargando y el subárbol derecho indica que se está cargando. La solución óptima se obtiene recuperando el árbol de soluciones del problema. y utilice el límite superior del nodo para eliminar los nodos que no cumplan con los requisitos. #include estructura buena { int peso int beneficio; ; int flag;//Si la bandera se puede cargar }; int number=0;//Número de elementos int upbound=0; int curp=0, curw=0;//Valor y peso del beneficio actual int maxweight=0; *bolsa =NULL; void Init_good() { bolsa=nuevo bien [número] for(int i; =0 ; i { cout<<"Por favor, introduzca el número del artículo"< cin>>bag[i].weight; cout<<"Ingrese el número de artículo"< cin >>bag[i].benefit; bag[i].flag=0;//La bandera inicial es no cargar en la mochila cout< } } int getbound(int num, int *bound_u)//Devuelve el límite c y el límite u de esto nodo { for(int w=curw, p=curp; num { w=w+bolsa[núm].peso p=w+bolsa[núm].beneficio } *bound_u=p +bolsa[núm].beneficio; retorno (p+bolsa[núm].beneficio*((maxweight-w)/bolsa[núm].peso) } void LCbag() { intbound_u=0,bound_c=0;//C límite y u límite del nodo actual for(int i=0; i { if( (bound_c=getbound (i+1, &bound_u))>upbound)//Atraviesa el subárbol izquierdo upbound=bound_u;//Cambia el límite u existente sin cambiar la bandera if( getbound( i, &bound_u)>bound_c )//Atraviesa el subárbol derecho //Si está cargado, determina si el límite c del subárbol derecho es mayor que el límite c de la raíz del subárbol izquierdo, si es así, cárguelo { upbound=bound_u;//Cambiar el límite u existente curp=curp +bag[i].benefit; curw= curw+bag[i].weight;//Agregar nuevos artículos a partir del peso y beneficios existentes bag[i].flag= 1;/ / Marcar para cargar } } } void Display() { cout<<"La cantidad de elementos que se pueden poner en la mochila es:" for(int i=0; i ; if( bolsa[i].flag>0) cout< cout< eliminar [ ]bolsa ; }