DBOY dynamic programming

, , ,
1

#include<stdio.h>
#include
#include
#include
#include
#include<unordered_map>

using namespace std;

int main(){

int t,n;

cin>>t;

while(t--){
    cin>>n;
    int di[n],fu[n];
    int dp[1001];
    for(int i=1;i<=1001;i++) dp[i]=0;
    int ma = -1,ch=1e9;
    for(int i=0;i<n;i++) {
        cin>>di[i];
        if(ma<di[i]) ma = di[i];
        if(ch>di[i]) ch = di[i];
    }
    for(int i=0;i<n;i++){
        cin>>fu[i];
        if(dp[fu[i]]==0) dp[fu[i]] = 1;
    }
    for(int i=ch;i<=2*ma;i++){
        int mini = 1e9;
       // cout<<dp[i]<<" ";
        if(dp[i]==0){
              for(int j=n-1;j>=0;j--){
          //  cout<<i<<" - "<<j<<endl;
            if(i>=fu[j]){
                if(mini>(1+dp[i-fu[j]]) && dp[i-fu[j]]!=0){
                mini = 1+dp[i-fu[j]];
                dp[i] = mini;
                }
            }
        }   
        }
    } 
    //for(int i=1;i<=2*ma;i++) cout<<dp[i]<<" ";
    int sum = 0;
    for(int i=0;i<n;i++){
        sum = sum + dp[di[i]*2];
    }
    cout<<sum<<endl;
}

return 0;

}

Has someone come across the reduce to one dynamic problem ? I used that strategy in the Pizza Delivery Boy (DBOY) problem , can someone point out what is going wrong here ?

2

Hello @lavanpuri ,
I want to give you some suggestion mate,

  1. Do not paste the code in the topic if it is not well-formatted.
  2. Let’s remove our debugging code before sending it to someone as it will add up unnecessary code.
    These suggestions are purely mine, and it’s okay if you don’t consider it.

Coming to your question
Yes, i have rectified your code. As i solved this question earlier in the day, i was able to notice your mistakes.
SOL

3

Hey @anon88305577 , thanks for the help.
Also thanks for the suggestions , i’m just a beginner , will keep them in mind.

1 Like