For this assignment, write, test, and execute code to solve the following problems. You should also answer all of the questions.

One of the more interesting problems that often comes up in resource utilization problems is known as the knapsack problem (which comes from the problem that many hikers face in trying to fit the most that they can into a knapsack, or backpack). We often run into problems where we only have a finite amount of one or more resources and need to find a good (or perhaps the best) solution given our constraints. Or, perhaps sometimes you simply want to spend exactly a certain amount (https://xkcd.com/287/)

This problem is interesting in that while there is not an optimal solution, there are a variety of good solutions involving variations of dynamic programming using recursive solutions.

Consider the following table of possible experiments to be considered as a payload for a flight in the space shuttle.

Number	Experiment	Weight (in kilograms)	Rating
1	Cloud Patterns	36	5
2	Solar Flares	264	9
3	Solar Power	188	6
4	Binary Stars	203	8
5	Relativity	104	8
6	Seed Viability	7	4
7	Sun Spots	90	2
8	Mice Tumors	65	8
9	Microgravity Plant Growth	75	5
10	Micrometeorites	170	9
11	Cosmic Rays	80	7
12	Yeast Fermentation	27	4

The space shuttle could lift 700 kg of material into near earth orbit. The question you are to investigate is what combination of payloads gives the highest overall rating. (In real life, weight is only one limitation considered, there are a variety of other possible limitations such as physical size, and power consumption to name a few).

There are a variety of ways that you could approach this problem, Id like you to try several. First, what is the total rating that you would achieve if you simply chose items with the highest rating first (you could do this by sorting, in a loop, by using a container class ). The second is to select items from the lightest to the most massive, a third might be to select experiments based on the ratio of rating to mass.

If you select experiments based on weight, what is the subset of experiments that you select, and what is the total rating of the experiments?

If you select experiments based on rating, what is the subset of experiments that you select and what is the total rating?

Describe at least one other approach that you could use to select experiments. If you chose to code this, what is the subset of experiments that you select and what is the total rating?

As we saw in class and in the text, if I have a collection of n items in a set, I get 2ⁿ possible subsets. While in general, an exponential time solution is not good, this is a small enough set that we can brute force this, (the array generator you created for the second programming exercise would be useful here).

Out of the 4096 possible subsets, what is the one with the highest rating?

While for even small sets of a few hundred n, we cant brute force this, there are good approaches that can provide good, though not optimal, solutions in much less than exponential time. This is actually one of the cases where using recursion (by using dynamic programming) actually gets commonly used.

Describe, in your own words, a dynamic programming algorithm that gives a good solution to the knapsack problem. If you have the time, and are interested, you can even present code which solves your problem.