0

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 ?

Improve this question
2
  • I think the binary search solution for this problem is indeed using memoization, but it doesn't form any overlapping subproblems in this case. At every stage, you are just dividing the books between given students and in the end, picking out minimum possible maximum books. I don't think DP is in fact required to be applied here. Commented Aug 13, 2017 at 8:54
  • You forgot to copy-and-paste the critical piece of information that makes this amenable to efficient DP: the fact that the books allocated to a student must be contiguous. Admittedly, this was buried in a note about something else in the original link, but still -1 for effort. Commented Aug 13, 2017 at 13:57

2 Answers 2

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

If I understood your solution correctly, here is a counterexample: M = 2, N = 3, P = [2, 4, 3]. f(1, 1) = 2; f(2, 1) = 6. So f(3, 2) must be either max(f(2, 1), 3) = 6 or max(f(1, 1), 7) = 7. But the correct answer is 5.
@user3290797 The answer is 6. Groups must be continuous. You can't put 2 and 3 together.
Where does it say that groups must be contiguous? It seems to be implicit in the worked example given at the bottom of the linked problem, but nothing I can see in the problem statement suggests this constraint.
@j_random_hacker If you open the link in the post, it says that the groups must continuous.
OK, I see it now -- buried in a "note" about something else! +1 for you, and no-effort-copy-and-paste + yet-still-manage-to-omit-critical-information = -1 for this question.
0 
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;
}
Improve this answer

1 Comment

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.