a bit of dp: SPOJ - SCUBADIV

Problem Statement
SPOJ - SCUBADIV

Summary
We are given \(N \leq 1000\) choice of air tanks having oxygen capacity, nitrogen capacity, and weight O[i], N[i], and W[i] respectively. \(O \leq 21, N \leq 79, W \leq 800\). We need enough tanks to fuel \(t, a\) oxygen and nitrogen respectively to complete the dive. Find the minimum total weight of tanks needed to complete the dive.

Solution:
This is a 0-1 knapsack problem. There is an interesting bottom-up approach to solving this problem in the case where you already overshoot the constraints (you have more nitrogen/oxygen than you need) by making use of the zero-indexes.

/* a[k][0..2] stores oxygen, nitrogen, weight resp.
    dp[k][i][j] is the minimum weight needed to reach
    i oxygen and j nitrogen (may overshoot) using k equipment
*/
for(int k=0;k<=N;++k){
    for(int i=0;i<=21;++i){
        for(int j=0;j<=79;++j){
            if(k==0) {
                dp[k][i][j] = INF;
                if(i==0 && j==0) dp[k][i][j] = 0;
            } else {
                dp[k][i][j] = min(dp[k-1][i][j], a[k][2] + dp[k-1][max(0,i-a[k][0])][max(0,j-a[k][1])]);
            }
        }
    }
}
return dp[N][T][A];