Jestem nowicjuszem w programowaniu dynamicznym i wypróbowałem tutaj w SPOJ całkowity problem plecakowy(http://www.spoj.pl/problems/KNAPSACK/). Jednak dla danych przypadków testowych moje rozwiązanie nie daje poprawnego wyjścia. Byłbym wdzięczny, gdybyś mógł zasugerować, czy następująca przeze mnie implementacja jest poprawna. Zwróć uwagę, że zmiennaback jest do śledzenia wstecznego, o którym nie wiem, jak to zrobić. Mam nadzieję, że również pomogę ci we wdrażaniu śledzenia wstecznego. Dzięki.

#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;
}

Oto poprawne przypadki testowe wejścia / wyjścia:

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


Output:
13

Jednak wyniki, które otrzymuję, to17.