Help required in DP problem

Правка en1, от thequacker, 2024-08-17 08:06:28

Problem Link

void solve(){
    int n,x;
    cin>>n>>x;
    vector<int>c(n),h(n);
    for(int i=0;i<n;i++){
        cin>>c[i]>>h[i];
    }

    int max_h=accumulate(h.begin(),h.end(),0ll);
    vector<int>dp(max_h+1,1e9);

    dp[0]=0;
    // 0 i i i i i i 
    for(int i=0;i<n;i++){
        for(int j=max_h;j>=0;j--){
            if(j-h[i]>=0 && dp[j-h[i]]+c[i]<=i*x){
                dp[j]=min(dp[j-h[i]]+c[i],dp[j]);
            }
        }
    }
    for(int i=max_h;i>=0;i--){
        if(dp[i]<=(n-1)*x){
            cout<<i<<endl;
            break;
        }
    }
}

why is the loop being runned from max_h to 0 and not 0 to max_h?
because we clearly need dp[j-h[i]] to compute dp[j]
if possible can someone explain this problem in depth?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский thequacker 2024-08-17 08:06:28 880 Initial revision (published)