Решение целочисленного рюкзака

Question

Я новый для динамического программирования и попробовал проблему с целочисленным рюкзаком здесь, в SPOJ (http://www.spoj.pl/problems/KNAPSACK/). Однако для данных тестов мое решение не дает правильного вывода. Я был бы благодарен вам, если бы вы могли предположить, правильно ли реализована следующая реализация. Обратите внимание, что переменная back предназначена для обратного отслеживания, о которой я не знаю, как это сделать. Я надеюсь, что и ваша помощь в реализации backtracking тоже. Благодарю.

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

Вот правильные тестовые случаи ввода/вывода:

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


Output: 
13 

Однако вывод, что я получаю 17.

Answer 1

Это версия проблемы с рюкзаком, известной как рюкзак 0-1.

Вы делаете глупые ошибки в своем коде.

Для начала с первым целым числом на входе указан вес, а второй - значение. Пока вы принимаете сначала значение, а второе - вес. Кроме того, вы принимаете значения n + 1 как входные значения от 0 до N включительно.

Теперь в вашем алгоритме вы считаете, что можете взять любое количество копий элементов, это не так, это ранец 0-1. Прочитайте это http://en.wikipedia.org/wiki/Knapsack_problem.

Я придумал этот алгоритм, и я представил его и принял. Так что это должно работать нормально.

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

BTW не динамически выделять массивы просто использовать векторы

vector <int> My_array(n); 

Answer 2

Существует версия проблемы с рюкзаком, хорошо документированная на https://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-p в Python.

EDIT: Nevermind, я пропустил часть, где первый вход линии определяет C и N. При этом ваш пример ввода не загружается с кодом, который вы предоставили (он ищет еще одну пару, чем будет ожидается из-за < = N). Я ожидаю, что этот цикл должен быть < N, чтобы получить 0..n-1 как элементы.

Фиксация, что я получил результат 134516145, который является бессмысленным.