0

The program is of dynamic programming.... Given n gold bars, find the maximum weight of gold that fits into a bag of capacity W. the code works fine on the given test cases and also test cases run by me on my PC. whats the problem? My code for explaination

#include<iostream>
typedef long long int ll;
using namespace std;

int main()
{
        ll w,n;
        cin>>w>>n;

        ll g[n];
        for(ll i=0;i<n;i++)
        {
                cin>>g[i];
        }

        ll arr[n+1][w+1];



        for(ll i=0;i<=n;i++)
        {
                for(ll j=0;j<=w;j++)
                {
                        if(j==0||i==0)
                        {
                                arr[i][j]=0;
                                continue;
                        }
                        else if(i>=1)
                        {
                                if(j-g[i-1]>=0)
                                {
                                        arr[i][j]=max((arr[i-1][j-g[i-1]])+g[i-1],arr[i-1][j]);
                                        continue;
                                }
                                else if(j-g[i-1]<0)
                                {
                                        arr[i][j]=arr[i-1][j];
                                        continue;
                                }

                        }
                }
        }


        cout<<arr[n][w]<<"\n";
}
Chirag Tejwani
  • 1
  • 1
  • 2
    Prefer [C++ Books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) to _competitive programming_ websites. – Ron May 12 '20 at 11:36
  • 4
    Variable-length arrays are non-standard and will cause stack overflows if you don't keep them small. Use `std::vector`. – molbdnilo May 12 '20 at 11:38
  • 2
    `typedef long long int ll;` is good to make your code hard to read, what else you try to achieve with it is unclear to me. Also single letter variable names are not nice – 463035818_is_not_an_ai May 12 '20 at 11:38
  • 1
    You don't need to explicitly `continue` a loop in every branch. (You lost all the typing you saved with that typedef.) – molbdnilo May 12 '20 at 11:42

0 Answers0