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.