Provide algorithm to solve recurrence and its complexity.

Question

Suppose air travel restrictions specify that one can pack in at most k items from a specifies “problem set” of items B. Additionally you have a set of unrestricted items A. Let A U B =S where S={ 8,8,…..,8}. Each item has weight w and provides benefit b. Set up a dynamic programming recurrence to solve the problem of packing your suitcase with maximum weight W in order to maximize your benefit. Provide the algorithm to solve the recurrence and its complexity.

Summary

Here in the given problem, we have to Provide the algorithm to solve the recurrence and its complexity. In which we have Two sets that will represent items that are allowed and the items which are restricted. Where items will also have weight. Now we will set up a dynamic programming recurrence to solve the problem.

Explanation

Basically, we have to write an algorithm for items that have weight but are also beneficial for travelling.
Let’s begin with the explanation of the algorithm.
We will consider the maximum value of weight is 5
Now consider the weights are in the following form such as {1,2,3}
And the benefits are {A,B,C} {a,b,c}
Now alphabets in uppercase has higher priority and alphabets in lowercase has a lower priority
here we take the weights in number and benefit in alphabets

The first row is of the weights and from second it will be of benefits.
0 1 2 3 4 5
a A d b B c
b B B a c C
c C A B A C
a b c A B C
Here, the maximum will be A, B and C.

Algorithm

function highestEarns(H, weight[], benefit[], int size)
Y[size +1][H+1] it allocates memory
For every k from 0 to size
For every w from o to H
If k=0 or h=0
Y[k][h] = 0
Else if weight[k-1] <= h
Y[k][h] = maximum((benefit[k-1]+Y[k-1][w-weight[k-1]), Y[k-1][w])
Else
Y[k][h] = Y[k-1][h]
Return Y[n][h]

Now here we have the time complexity of O(size * W), Because we can see there are two for loop which we can call a nested for loop.

Also read, use the truth tables method.