Soy nuevo en la programación dinámica y he probado el problema de las mochilas con números enteros 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 agradecería si pudiera sugerir si la siguiente implementación de mi parte es correcta. Tenga en cuenta que la variableback es para dar marcha atrás, sobre lo cual no estoy seguro de cómo hacerlo. Espero contar con su 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;
}

Aquí están los casos de prueba de entrada / salida correctos:

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


Output:
13

Sin embargo, la salida que estoy obteniendo es17.