Reputation: 2535
Can the "allocate minimum no of pages" problem be solved using DP?
You are given N number of books. Every ith book has Pi number of pages. You have to allocate books to M number of students. There can be many ways or permutations to do so. In each permutation one of the M students will be allocated the maximum number of pages. Out of all these permutations, the task is to find that particular permutation in which the maximum number of pages allocated to a student is minimum of those in all the other permutations, and print this minimum value.
Each book will be allocated to exactly one student. Each student has to be allocated at least one book.
I know it will be unoptimised and binary search solution is more efficient, but for my understanding can this be solved and if yes what will be the memoization step or temp array and how problem will be broken down in bottom up manner to solve using DP ?
Upvotes: 0
Views: 1813
Reputation: 1
vector<vector<int>> dp;
int minpages(int n,int m,int arr[])
{
if(dp[n][m]!=-1) return dp[n][m];
if(n<m) return dp[n][m]=INT_MAX;
if(n==0 && m==0) return dp[n][m]=0;
if(n==0 || m==0) return dp[n][m]=INT_MAX;
int min_val=INT_MAX;
for(int j=n;j>=0;j--)
{
min_val=min(min_val,max(accumulate(arr+j,arr+n,0),minpages(j,m-1,arr)));
}
return dp[n][m]=min_val;
}
Upvotes: 0
Reputation: 18556
Yes, one can solve it using dynamic programming.
Let f(b, s)
be the minimum value of the maximum number of pages one student has to read given that we have distributed the first b
books among s
students.
The base case is f(0, 0) = 0
: no students, no books, no pages.
The transition look this way: if the current state is (b, s)
, we can go to a new state (new_b, s + 1)
(where new_b > b
) and set its cost to max(f(b, s), sum_of_pages[b + 1, new_b])
. It means that we assign all books in the [b + 1, new_b]
range to the next student.
The answer is f(N, M)
(it means that we've processed all books and assigned them to all students).
The intuition behind this solution is as follows: if we've assigned the first b
books, the only thing that matters to us is the number of students who've already been assigned some books and the current answer. It doesn't matter how this assignment looks exactly.
Upvotes: 1