## Wednesday, October 1, 2014

### a bit of dp: SPOJ - SCUBADIV

Problem Statement

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];