You have n programs p1, ..., pn with size s1, ..., sn MB (mega bytes). You have

Question

You have n programs p1, ..., pn with size s1, ..., sn MB (mega bytes). You have a disk that can store up to T MB. T is less than the total size of the programs. You are asked to use a dynamic programming solution to store the programs onto the disk so as to maximize the disk space utilization. In other words, you want to find a subset of programs such that its total size is maximized but has to be less than T.

Define U[i,t] as the maximum disk utilization of a disk with capacity t MB and programs p1,...,pi to be selected for storing it on the disk. Write a recurrence for U[i,t] and identify the boundary condition.

Explanation / Answer

replacing T here with s

Assume that it doesn

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.