Resolviendo la mochila entera

Question

Soy nuevo en la programación dinámica y he intentado con el problema entero de la mochila aquí en SPOJ (http://www.spoj.pl/problems/KNAPSACK/). Sin embargo, para los casos de prueba dados, mi solución no está dando el resultado correcto. Le estaría agradecido si pudiera sugerir si la siguiente implementación por mí es correcta. Tenga en cuenta que la variable back es para retroceder, sobre la que no estoy seguro de cómo hacerlo. Espero contar con tu ayuda para implementar el backtracking también. Gracias.

#include <cstdio> 
#include <cstdlib> 
#include <algorithm> 
#include <vector> 
#include <string> 
#include <iostream> 

using namespace std; 

int knapsack(int value[], int weight[], int n, int C, 
     vector <int>&back) 
{ 
    int *M = new int[C + 1]; 
    int k; 
    int i, j, tmp, pos; 
    for (i = 1; i <= C; i++) { 
     M[i] = M[i - 1]; 
     pos = i - 1; 
     for (j = 0; j < n; j++) { 
      k = i - weight[j]; 
      if (k >= 0) 
       tmp = M[k] + value[j]; 
      if (tmp > M[i]) { 
       M[i] = tmp; 
      } 
     } 
     back.push_back(pos); 
    } 
    int ans = M[C]; 
    delete[]M; 
    return ans; 
} 


int main() 
{ 
    int C, N; 
    cin >> C >> N; 
    int* value = new int[N+1]; 
    int* weight = new int[N+1]; 
    for (int i = 0; i <= N; i++) { 
     cin>>value[i]>>weight[i]; 
    } 
    vector <int>back(N, 0); 
    cout<<knapsack(value,weight,N,C,back)<<endl; 
    return 0; 
} 

Éstos son los casos de prueba correctos de entrada/salida:

Input: 
4 5 
1 8 
2 4 
3 0 
2 5 
2 3 


Output: 
13 

Sin embargo, la salida que estoy recibiendo es 17.

Answer 1

Esta es una versión del problema Knapsack conocido como la mochila 0-1.

Estás cometiendo algunos errores tontos en tu código.

Para comenzar con el primer entero en la entrada es el peso y el segundo es el valor. Mientras toma primero como valor y luego como peso. Además, está tomando valores n + 1 como entrada 0 a N inclusive.

Ahora en su algoritmo, usted está considerando que puede tomar cualquier número de copias de los elementos, esto no es cierto, esto es una mochila 0-1. Lea esto http://en.wikipedia.org/wiki/Knapsack_problem.

Se me ocurrió este algoritmo y me presenté y me aceptaron. Entonces esto debería funcionar bien.

int M[2000][2000]; 
int knapsack(int value[], int weight[], int C, int n) 
{  
    for(int i = 1; i <= C; i++){ 
    for(int j = 0; j <n; j++){ 
     if(j > 0){ 
     M[j][i] = M[j-1][i]; 
     if (weight[j] <= i) 
      M[j][i] = max(M[j][i], M[j-1][i-weight[j]]+value[j]); 
     } 
     else{ 
     M[j][i] = 0; 
     if(weight[j] <= i) 
      M[j][i] = max(M[j][i], value[j]); 
     } 
    } 
    // cout << M[i][n-1] << endl; 
    }   
    return M[n-1][C]; 
} 

int main() 
{ 
    int C, N; 
    cin >> C >> N; 
    // cout << C << endl; 
    int* value = new int[N+1]; 
    int* weight = new int[N+1]; 
    for (int i = 0; i < N; i++) { 
     cin>>weight[i]>>value[i]; 
    } 
    // vector <int>back(N, 0); 
    cout<<knapsack(value,weight,C,N)<<endl; 
    return 0; 
} 

Por cierto no asignan dinámicamente matrices sólo tiene que utilizar vectores

vector <int> My_array(n); 

Answer 2

Hay una versión del problema de mochila bien documentada en https://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-p en Python.

EDITAR: No importa, omití la parte donde la entrada de la primera línea define C y N. Dicho esto, su ejemplo de entrada no parece cargarse con el código que proporcionó (está buscando un par más de lo que sería esperado debido al < = N). Espero que ese ciclo sea < N, para obtener 0..n-1 como elementos.

Reparado que obtengo un resultado de 134516145 impreso, que no tiene sentido.