CODEWITHSUNDEEP
c++algorithmdynamic-programming
alDiablo
alDiablo

Reputation: 979

WA in scubadiv spoj (top down dp)

I am stuck on this question getting WA.

I have seen many bottom up implementations of this question. My top-down implementation is not working with memoization and is working fine without it. How can i correct it ?? 

#include<cstdio>
#include<cstring>
#include<iostream>

#define INF 0x7FFFFFFF

using namespace std;

int o,n,num,ox[2000],nt[2000],wt[2000];
int dp[2000][2000];

int dive(int index,int oxygen,int nitrogen,int weight) {
    if(dp[oxygen][nitrogen]!=-1) return dp[oxygen][nitrogen];
    int &ret=dp[oxygen][nitrogen];
    if(oxygen>=o&&nitrogen>=n) {
        ret=weight; 
        return ret;
    }
    if(index==num) {
        ret=INF;
        return ret;
    }
    ret= min(dive(index+1,oxygen+ox[index],nitrogen+nt[index],weight+wt[index]),dive(index+1,oxygen,nitrogen,weight));  
    return ret;
}

main() {
    int c;
    scanf("%d",&c);
    while(c--) {
        memset(dp,-1,sizeof(dp));
        scanf("%d%d",&o,&n);
        scanf("%d",&num);
        for(int i=0;i<num;++i) {
            scanf("%d%d%d",&ox[i],&nt[i],&wt[i]);
        }
        printf("%d\n",dive(0,0,0,0));
    }
    return 0;
}

Upvotes: 1

Views: 503

Answers (2)

saravanan
saravanan

Reputation: 408

This gives wrong answer too :( could someone check pls

    #include<iostream>
    using namespace std;
    int swap( int &a,int &b)
    {
       int temp=a;
       a=b;
       b=temp;
    }
    int min(int a, int b)
    {
    if(a<b)return a;else return b;
    }
    int max(int a,int b) 
    {
    if(a>b)return a;else return b;
    }
    int minweight(int ans[][22][80],int arr[][3],int n,int oxy,int nit)
    {
     int prev=0,curr=1;

    for(int i=1;i<=n;i++)
    {

        for(int j=0;j<=21;j++)
            for(int k=0;k<=79;k++)
                ans[curr][j][k]=min( ans[prev][j][k], arr[i][2]+ans[prev][max(0,j-arr[i][0])][max(0,k-arr[i][1])]);
        swap(curr,prev);
}


        return ans[n&1][oxy][nit];
    }
   int main()
   {
    int cases;
    cin>>cases;

    while(cases--)
    {
        int oxy,nit;
        cin>>oxy>>nit;
        int n;
        cin>>n;
        int arr[n+1][3];
        for(int i=1;i<=n;i++)
        {
            cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
        }   
        int ans[2][22][80];

            for(int j=0;j<oxy+1;j++)
                for(int k=0;k<nit+1;k++)
                    ans[0][j][k]=9999;
            ans[0][0][0]=0;

        cout<<minweight(ans,arr,n,oxy,nit);
    }

}

Upvotes: 0

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

Try this test:

1
21 79
5
1 1 800
1 1 800
1 1 800
1 1 800
17 75 800

It seems to me the correct answer for it should be 800 * 5 = 4000 right? Your program outputs something else.

Upvotes: 1

Related Questions