It's about dynamic program proof problem

You have a collection of boxes and want to pack them in your attic. Every box i has a width Wi, a height hi and contains items of total value vi. Your attic has the shape of a right angled isosceles triangle with two sides of length H. You want to stack the boxes and place them in the attic. You may choose the order in which to stack the boxes but you are not allowed to rotate them and you cannot place two boxes side by side. However, not all boxes can fit in the attic. In order for a box to fit, its width must be at most H minus its height and the heights of all the boxes below it in the stack. Figure 1, illustrates how boxes are packed to fit in the attic. Your goal is to maximize the value of the boxes placed in the attic. H Figure 1: How boxes are stacked and placed in the attic. Input: A set of n boxes with box i having width Wi, height h; and value vi, the height of the attic H, where all heights his and H are integers. Your goal is to maximize the value of the boxes placed in the attic. (a) Assuming all boxes have the same height h = 1, give an efficient algorithm to find the optimal arrangement of boxes in the attic. Prove the correctness of your algorithm and analyze its runtime. (b) For the general case where all boxes have arbitrary integer heights, give an O(n logn+nH) algorithm to find the optimal arrangement of boxes in the attic. You have a collection of boxes and want to pack them in your attic. Every box i has a width Wi, a height hi and contains items of total value vi. Your attic has the shape of a right angled isosceles triangle with two sides of length H. You want to stack the boxes and place them in the attic. You may choose the order in which to stack the boxes but you are not allowed to rotate them and you cannot place two boxes side by side. However, not all boxes can fit in the attic. In order for a box to fit, its width must be at most H minus its height and the heights of all the boxes below it in the stack. Figure 1, illustrates how boxes are packed to fit in the attic. Your goal is to maximize the value of the boxes placed in the attic. H Figure 1: How boxes are stacked and placed in the attic. Input: A set of n boxes with box i having width Wi, height h; and value vi, the height of the attic H, where all heights his and H are integers. Your goal is to maximize the value of the boxes placed in the attic. (a) Assuming all boxes have the same height h = 1, give an efficient algorithm to find the optimal arrangement of boxes in the attic. Prove the correctness of your algorithm and analyze its runtime. (b) For the general case where all boxes have arbitrary integer heights, give an O(n logn+nH) algorithm to find the optimal arrangement of boxes in the attic