You’re a voracious reader with a large collection of books B = [b1 , b2 , . . .
ID: 3795789 • Letter: Y
Question
You’re a voracious reader with a large collection of books B = [b1 , b2 , . . . , bn ] and you’re going on vacation. You’ve already packed all your essentials and discovered that you have W grams left to fill up with books. Because you want to optimize your reading pleasure, you’ve rated every book b in your collection for enjoyment (e(b)) and then used a scale to find out how much each books weighs in grams (w(b)). You only have one copy of each book, and you are interested in maximizing the sum of the enjoyment values.
For example, suppose that W = 1000 and you are considering the following four books:
b1 b2 b3 b4 w 600 300 400 200
e 30 14 16 9
Then the optimal book selection consists of books b1 and b3, which together weigh exactly 1 kilogram and have
a total enjoyment of 46.
(a) Suppose that S = {b1 , b4 , b10 } is the set of books with maximum total enjoyment among all sets of books that weigh at most 1000 grams in total. Show that {b1,b4} is an optimal set of books among all sets of books that weigh at most 1000 w(b10) grams in total and only use books b1 through b9.
(b) Use the observation from 4a to give a recurrence for S(W, k): the maximum total enjoyment over all sets of books with total weight at most W that only use books b1 through bk.
(c) Give a dynamic programming algorithm that computes the maximum total enjoyment over all sets of books that weigh at most W grams.
(d) Analyze the running time of your algorithm.
(e) Is this running time polynomial in the size of the input? Why, or why not?
You have also classified each book in your collection into one of three genres: Classics, Fantasy, and Science Fiction. To make sure that your books aren’t too similar, you want to pack at least G books from each genre.
(f) Modify your recurrence from 4b to account for this new condition. (Hint: introduce three new variables, representing the number of books from each genre, up to G.)
(g) Modify your algorithm from 4c to account for this new condition.
Explanation / Answer
This type of problems are called (0-1) Knapsack problems. We can use they type of poblems to calculate the maximum amount in an array having some constraint on the information given to them. I have written the code for the problem above which u can find below.
#include<stdio.h>
// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }
// Returns the maximum enjoyment value with a constraint of maximum weight passed
int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[n+1][W+1];
// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}
return K[n][W];
}
//Main function of the program
int main()
{
int enj[] = {30,14,16,9}; //Initializing the enjoyment array which stores the enjoyment values of each book
int wt[] = {600, 300, 400, 200}; // Initializing the Wt array which shows the weights of all the books
int W = 1000;
int n = sizeof(enj)/sizeof(enj[0]);
//Prints the Maximum enjoyment value with a constraint of Maximum weight of 1000
printf("%d", knapSack(W, wt, enj, n));
return 0;
}
The Time complexity is O(NW) where N is the size of the books Array given and W is the Constraint passesed which is the Maximum weight limit. By clearly seeing the code above U can unterstand this.
By urderstanding the above code we can clearly say that suppose if S = {b1 , b4 , b10 } is the set of books with maximum total enjoyment among all sets of books that weigh at most 1000 grams in total, {b1,b4} is an optimal set of books among all sets of books that weigh at most 1000 w(b10) grams in total and only use books b1 through b9.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.