dynamic programming (backpack problem)

[StGuru]

I got the code in c++ for the backpack problem.

#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.

[ProgramArtist]

...

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

[laserlight]

"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++.