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

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
    May 2006
    Location
    Dresden, Germany
    Posts
    458

    Re: dynamic programming (backpack problem)

    Quote Originally Posted by StGuru View Post
    ...

    Can somebody explain the suboptimal solutions, and how the problem is solved.

    Thanks in advance.

    +karma for the person who will help me.
    Can you explain your problem?

    Seeing your code I can give you some hints:

    • "long long" is nothing known to my c-compiler. What do you mean by it?
    • In c and c++ all arrays are zero based. The first elem of MyArray[10] is MyArray[0] and the last elem is MyArray[9].
    • I strongly recommend to use brackets after starting an if block!
    • The code is much better to read and understand, if you (1) ident it correctly and (2) give your variables more "speaking" names.


    If you have questions to the "backback problem" (also known as "knapsack problem" or "rucksack problem") you can find a good start in the Wikipedia.

    If you've a certain question feel free to ask. But "How can it be solved?" is not a certain question and btw: This question is answered in wikipedia's article.

    With regards
    Programartist

  3. #3
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,762

    Re: dynamic programming (backpack problem)

    Quote Originally Posted by ProgramArtist
    "long long" is nothing known to my c-compiler. What do you mean by it?
    But this is C++, not C. The 1999 edition of the C standard does provide for long long as at least a 64 bit integer type; this may also be available as a compiler extension for C++.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

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)