dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

Thread: dynamic programming (backpack problem)

  1. #1
    Join Date
    Mar 2009
    Posts
    82

    dynamic programming (backpack problem)

    I got the code in c++ for the backpack problem.
    Code:
    #include <iostream>
    using namespace std;
    
    int main()
    {
        long long int B[1000],C[1000];
        int V[100],Z[100],N,M,q,i;
        
        cin>>N>>M;
        
        for(i=1;i<=M;i++) cin>>Z[i];
    
       for(i=1;i<=M;i++) cin>>V[i];
        
        B[0]=0;
        C[0]=0;
    
        for (q=1;q<=N;q++)
        {
            B[q]=0;
            C[q]=0;
    
        for(i=1;i<=M;i++)
    
        if (Z[i]<=q)
    
         if (B[q-Z[i]]+V[i]>B[q]) 
         {
    
         B[q]=B[q-Z[i]]+V[i];
         C[q]=i;
    
         }
    
    }
        cout<<B[N]<<endl;
       
        
    return 0;
    }
    Can somebody explain the suboptimal solutions, and how the problem is solved.

    Thanks in advance.

    +karma for the person who will help me.

  2. #2
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    Re: dynamic programming (backpack problem)

    I think you better ask in Algorithm forum.
    Thanks for your help.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)