AutoSave

Home

Insert

Draw

Design

$-.$

assignment Dynamic programming $$ Saved to my Mac $$

Search $(Cmd+Ctrl+U)$

Calibri $($Bo$...$

$11$

Layout

References

Mailings

Review

View

Comments

AaBbCcDdEe

AaBbCcDdEe

AaBbCcDc

AaBbCcDdE $lon$

Paste

B

I

Normal

No Spacing

Heading $1$

Heading $2$

Styles

Dictate

Add$-$ins

CSL $3111$ : Assignment: Uynamic programming $($b marks$)$

Due Nov $26($to be handed AS a Hard Copy during lecture$)$

A production company has to ship items of various weights $v_i,1in$ on a truck. There is a max weight $x$ that the truck can take. Assume that there is an unlimited supply of each item. The company wants to understand how many different ways there are to pack the truck. There is no volume$/$size limit and the order the items go onto the truck does not matter.

For example, the set of weights might be $\{1,3,4,7\}$ and $x=10$ then some of the possible ways to fill the truck are:

$\{7,3\}$

$\{7,1,1,1\}$

$\{4,4,1,1\}$

$\{4,3,3\}$

$\{4,3,1,1,1\}$

$\{4,1,1,1,1,1,1\}$

$\{1,1,1,1,1,1,1,1,1,1\}$ etc.

Give a dynamic programming algorithm to solve this problem. Make sure that you describe in words the subproblems you are building your optimal solution from, you give a recurrence relation as well as pseudocode and both the time and space complexity. Your correctness relies on your explanation of the correctness of your recurrence relation and need not be formal but should be clear.