इंटेगर नॅपैकैक को हल करना

Question

मैं गतिशील प्रोग्रामिंग के लिए एक नया हूं और एसपीओजे (http://www.spoj.pl/problems/KNAPSACK/ पर पूर्णांक knapsack समस्या का प्रयास किया है)। हालांकि, दिए गए परीक्षण मामलों के लिए मेरा समाधान सही आउटपुट नहीं दे रहा है। यदि आप सुझाव दे सकते हैं कि मेरे द्वारा निम्नलिखित कार्यान्वयन सही है तो मैं आपका आभारी हूं। कृपया ध्यान दें कि परिवर्तनीय back बैकट्रैकिंग के लिए है, जिसके बारे में मुझे यकीन नहीं है कि कैसे करना है। मुझे उम्मीद है कि बैकट्रैकिंग को लागू करने में आपकी मदद भी होगी। धन्यवाद।

#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 knapsack के नाम से जाना जाता है।

आप अपने कोड में कुछ मूर्खतापूर्ण गलतियां कर रहे हैं।

इनपुट में पहले पूर्णांक के साथ शुरू करने के लिए वजन और दूसरा मूल्य है। जबकि आप पहले वजन के रूप में मूल्य और दूसरे के रूप में ले रहे हैं। इसके अलावा आप एन + 1 मान एन इनपुट सहित इनपुट 0 के रूप में ले रहे हैं।

अब आपके एल्गोरिदम में, आप इस बात पर विचार कर रहे हैं कि आप वस्तुओं की किसी भी प्रतियां ले सकते हैं, यह सच नहीं है कि यह 0-1 knapsack है। इसे 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 पर अच्छी तरह से प्रलेखित knapsack समस्या का एक संस्करण है।

संपादित करें: कभी नहीं, मैंने उस भाग को छोड़ दिया जहां पहली पंक्ति इनपुट सी और एन को परिभाषित करता है। उसने कहा, आपका इनपुट उदाहरण आपके द्वारा प्रदान किए गए कोड से लोड नहीं होता है (यह एक और जोड़ी की तलाश में है < = एन) के कारण अपेक्षित। मुझे उम्मीद है कि लूप < एन होना चाहिए, आइटम के रूप में 0..एन -1 प्राप्त करने के लिए।

यह तय करना कि मुझे 134516145 मुद्रित परिणाम मिल गया है, जो गैरकानूनी है।