0

I've been trying to learn dynamic programming on c++, and this is my first project on that (knapsack problem) Please help me understand why I'm getting these errors.

This is my code:

#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int knap(int n, int wt[], int price[], int W){          // n = number of items; size of array, w = wt available in knapsack
                                                        // wt stores weight if items, price:price

        // base case
        if(n == 0 || W == 0){
            return 0;
        }
        if(wt[n-1] <= W){           // condition for adding item to knapsack (wt of item must be less than space remaining in knapsack)

            return max((price[n-1] + knap(n-1, wt[], price[], W - wt[n-1])), knap(n-1, wt[], price[], W)) ;  // max wrt recursion from previous element
        }
        else if(wt[n-1] > W){
            return knap(n-1, wt[], price[], W);
        }

}

int main(){
    fastio

    cout<<knap(4, [4, 8, 5, 3], [5, 12, 8, 1], 10);
}

These are the errors:

||=== Build file: "no target" in "no project" (compiler: unknown) ===|
F:\C++\c++\DP\knapsack.cpp||In function 'int knap(int, int*, int*, int)':|
F:\C++\c++\DP\knapsack.cpp|14|error: expected primary-expression before ']' token|
F:\C++\c++\DP\knapsack.cpp|14|error: expected primary-expression before ']' token|
F:\C++\c++\DP\knapsack.cpp|14|error: expected primary-expression before ']' token|
F:\C++\c++\DP\knapsack.cpp|14|error: expected primary-expression before ']' token|
F:\C++\c++\DP\knapsack.cpp|16|error: expected ']' before ')' token|
F:\C++\c++\DP\knapsack.cpp|17|error: expected primary-expression before ']' token|
F:\C++\c++\DP\knapsack.cpp|17|error: expected primary-expression before ']' token|
F:\C++\c++\DP\knapsack.cpp||In function 'int main()':|
F:\C++\c++\DP\knapsack.cpp|25|error: expected identifier before numeric constant|
F:\C++\c++\DP\knapsack.cpp|25|error: expected ']' before ',' token|
F:\C++\c++\DP\knapsack.cpp|25|error: expected '{' before ',' token|
F:\C++\c++\DP\knapsack.cpp||In function 'int main()':|
F:\C++\c++\DP\knapsack.cpp|25|error: expected ')' before ']' token|
||=== Build failed: 11 error(s), 0 warning(s) (0 minute(s), 1 second(s)) ===|

I'm new to c++, just moving here from python, so if possible, please explain with that in consideration.

Scheff's Cat
  • 19,528
  • 6
  • 28
  • 56
Dudeness
  • 97
  • 5
  • Please don't add the C tag for C++ questions; they're different languages, and both tags are rarely applicable on a single question. – cigien May 05 '21 at 12:41
  • sorry, will make required change – Dudeness May 05 '21 at 12:42
  • 4
    `cout< – Lukas-T May 05 '21 at 12:44
  • 4
    May I suggest getting [a good C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) instead of whatever website you are using? You are lacking the very basics of working with arrays, and this competitive programming website will not teach you that. – Yksisarvinen May 05 '21 at 12:44
  • *sorry*, just moved here from python – Dudeness May 05 '21 at 12:46
  • @churill, is this better? – Dudeness May 05 '21 at 12:50
  • 4
    Your Python experience may be valuable for making an algorithm but it's rather worthless concerning the syntax and semantics of C++. (Considering that it's full of pitfalls and opportunities for Undefined Behavior, the hint with the C++ book is the better one.) I somehow got your code running but, please, pay attention to the left warning: [Demo on coliru](http://coliru.stacked-crooked.com/a/2323de78cd07f1b8) and there are still some other Don'ts left... – Scheff's Cat May 05 '21 at 12:50
  • 2
    _is this better?_ Not really. While a `std::vector` isn't that bad, you cannot pass it as is where an `int*` is expected. Try to compile and look what your C++ compiler thinks about this. – Scheff's Cat May 05 '21 at 12:51
  • 2
    please do not change the code in your question in a rush. After you changed the code, the error message is not what you get from that code. Others make suggestions because they want to help you, but editing those suggestions into the code in the question does not help that much. – 463035818_is_not_an_ai May 05 '21 at 12:54
  • 1
    Looking at your code again, I became aware of how to fix the warning: `if (wt[n-1] <= W) {` ... `} else if (wt[n-1] > W) {` ... `}`. What other case might be existing? None. If something is not `<= W` it's `> W` (at least for integral values to which `W` belongs to). Change the second `else if` to just an `else` and the compiler will stop its complaints: [Demo on coliru](http://coliru.stacked-crooked.com/a/3498fad91e42558e) – Scheff's Cat May 05 '21 at 12:56
  • @Scheff another stupid doubt: when i predefine price and wt values, i get the correct ans (in this case, 13) but when i make a user input the elements of wt and price array, i get 9.. why? (```for(int i = 0; i>a[i]; ```) is what i use to input elements of array – Dudeness May 05 '21 at 13:22
  • 1
    In this case, something is wrong with your input, or your application exhibits Undefined Behavior. A deterministic algorithm should compute always the same output for the same input. If it doesn't it just isn't deterministic. Undefined Behavior might be a reason why a C++ function doesn't act as deterministic as it should. – Scheff's Cat May 05 '21 at 14:27

1 Answers1

1

Replace the return statement

return max((price[n-1] + knap(n-1, wt[], price[], W - wt[n-1])), knap(n-1, wt[], price[], W));

with the following

return max((price[n-1] + knap(n-1, wt, price, W - wt[n-1])), knap(n-1, wt, price, W));

In C++ when we are passing an array to the function we use only the name of the array not the instance of the array...

Salahuddin Ahmed
  • 4,854
  • 4
  • 14
  • 35
parzeval l
  • 26
  • 1