WIPL Re-explanation

help
1

Please if someone can explain this more clearly?

Subtask 1
Knowledge of knapsack is not required for the first subtask. Create a dp array where dp[i][j][k]dp[i][j][k]dp[i][j][k] : the minimum number of boxes required to build two towers of height exactly i and j respectively, if we can only use the first k boxes. The recurrence relation for each height[i] will be :

dp[0][0][0] = 0;
int ans = INF;
// height is sorted in non-increasing order
for(int idx = 1; idx <= n; idx++){
    for(int i = MAX; i >= 0; i--)
        for(int j = MAX; j >= 0; j--){
            if(i >= height[idx-1])
                dp[i][j][idx] = min(dp[i][j][idx], dp[i - height[idx-1]][j][idx-1] + 1);
            if(j >= height[idx-1])
                dp[i][j][idx] = min(dp[i][j][idx], dp[i][j - height[idx-1]][idx-1] + 1);
        }
}

then after the whole computation check the minimum value of dp[i][j]dp[i][j]dp[i][j] for all i,ji, j i,j ≥\geq≥ k k k.
This solution of time complexity O(N3)\mathcal O(N^{3})O(N3) will pass the first subtask.

2

Original link

3

Let me try again.
Let dp[i][j][idx] signify the minimum number of boxes required to create 2 pillars of height exactly i and j from the first idx boxes. Suppose there were 2 boxes of height 5 and 3

dp[0][0][0] = 0 (We need 0 boxes to create 2 pillars of height 0 and 0 respectively).
dp[5][0][1] = 1 (create a pillar of height 5 from the first 1 box).
dp[0][5][1] = 1 (same as above, just use the box in the second pillar)
dp[5][3][1] = 0 (We cannot create 2 pillars of height 5 and 3 from the first 1 boxes)
…
…
dp[5][3][2] = 1 (We can create 2 pillars of height 5 and 3 from the first 2 boxes)

In short whenever you are adding a box of index idx of height h_{idx} you can stack it upon the pillar created by idx-1 boxes of height i- h _{idx}, j or upon i, j - h_{idx} for all i, j. This is your dp recurrence relation.
I hope this makes sense now.

4

Trying to implement the same for subtask 1 is there something wrong?

Code & Results