what is wrong with the function parameter?

Question

#include <iostream>
using namespace std;

template<class Type>
void Knapsack(Type *v,int *w,int c,int n,Type **m)
{
 int i,j;
    int jMax=max(w[n]-1,c);
    for(j=0;j<=jMax;j++)
    m[n][j]=0;
for(j=w[n];j<=c;j++)
    m[n][j]=v[n];
for(i=n-1;i>1;i--)
{
    for(j=0;j<=w[i]-1;j++)
        m[i][j]=m[i+1][j];
    for(j=w[i];j<=c;j++)
    {
        m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
    }
}
m[1][c]=m[2][c];
if(c>=w[1])
    m[1][c]=max(m[2][c],m[1][c-w[1]]+v[1]);

}

template <class Type>
void TrackBack(Type **m,int *w,int c,int n,int *x){
for(int i=1;i<=n;i++)
{
    if(m[i][c]==m[i+1][c])
        x[i]=0;
    else
        x[i]=1;
}
}

int main()
{
int m[101][101]={0};
int x[101];
int n=5;
int c=10;
int w[5]={2,2,6,5,4};
int v[5]={6,3,5,4,6};

Knapsack(v,w,c,n,m);


return 0;
}

I an writing the algorithm of 01 Knapsack problem.

my Xcode says "No matching function for call to 'Knapsack' " I am stumbled by the red alarm.

I'm confused for passing arguments.

Is there anyone can help me? Thanks a lot:)

Please format your code properly - no one wants to wast time trying to make sense of badly formatted code. — Paul R, Apr 21 '15 at 11:32
An array of arrays of some type is *not* the same as a pointer to a pointer to the type. See e.g [this old answer of mine](http://stackoverflow.com/questions/18440205/casting-void-to-2d-array-of-int-c/18440456#18440456) for an explanation why. — Some programmer dude, Apr 21 '15 at 11:33

score 1 · Answer 1 · answered Apr 21 '15 at 11:33

1

This is not a valid conversion:

int m[101][101]
...
Knapsack(v,w,c,n,m);
              // ^-- expects a Type **m

m can decay to type "pointer to array of 101 ints", but no further.

answered Apr 21 '15 at 11:33

chi

111,837
3
133
218

Vlad from Moscow · Accepted Answer · 2015-04-21T11:44:00.823

At least type of argument

int m[101][101]={0};

is not equivalent to T ** where T is int.

When this array is passed by value as an argument it is implicitly converted to pointer to its first element and has type int ( * )[101]

Take into account that in any case this function is invalid. For example argument for second parameter w has 5 elements.

int w[5]={2,2,6,5,4};

The valid range of indices for it is [0,4]. n in the function call is equal to 5.

So this statement

int jMax=max(w[n]-1,c);

has undefined behaviour because you are using inadmissible index equal to 5.

template<class Type>
void Knapsack(Type *v,int *w,int c,int n,Type **m)
{
 int i,j;
    int jMax=max(w[n]-1,c);
//...

Thanks a lot for your answer. I couldn't give you upvote since I don't have enough reputation...... — skywhat, Apr 21 '15 at 11:54

score 0 · Answer 3 · answered Apr 21 '15 at 11:44

0

You a little bit wrong with definition of functions

template < class Type>
void Knapsack(Type *v,int *w,int c,int n,Type m[][101])

template < class Type>
void TrackBack(Type m[][101],int *w,int c,int n,int *x)

answered Apr 21 '15 at 11:44

POTEMKINDX

395
2
9

what is wrong with the function parameter?

3 Answers3