# Go语言代写 | CSI 2120 Programming Paradigm

这个作业是用Go语言解决背包问题

CSI 2120 Programming Paradigm

Problem description

This comprehensive assignment asks you to solve the Knapsack problem using the programming

paradigm seen in class.

This problem can be expressed as follows: given a set of items, each of them having a weight and a

value and given a knapsack (i.e. a container for items) having a maximal weight capacity, find the

subset of items to be added to the knapsack that maximizes the total value without exceeding the weight

capacity. Each item can be inserted just once and cannot be subdivided. Note that we will solve here the

problem for which the item weights are expressed in integer units. Mathematically the problem to solve

is the following:

Given two sets of n positive integers

Solving the problem

There are two possible strategies to solve this problem: a brute-force solution and a dynamic

programming solution. We will ask you to compare both in this assignment.

1. Brute force

Here the idea is simply to consider all possible solutions and select the one giving the highest value.

Indeed, the solution space for this problem can be represented by a binary tree in which each level is

associated to a specific item. For each item, we have to take a binary decision: should we include it in the

knapsack or not? This binary decision is represented by the two branches below each node of the binary

tree.

For example, considering the case given in the table at the top of this page, we can first consider item A.

We have two options: if we add it to the knapsack, then we have a current value of 1 and a residual

capacity of 6 (because item A has a weight of 1 and our knapsack has a capacity of 7). Now, let’s consider

the next item, that is item B (this is the second level of our solution tree). The first node of this level

corresponds to the case where we already have item A in the knapsack. If we also choose to add item B

then the new value is 7 and the residual capacity is 4. If we do not add item B, then we still have current

value at 1 and capacity at 6. The second node of this level is for the case where we have not added item A

to the knapsack. In that case if we add item B, then we have a current value of 6 and a residual capacity

of 5. Finally, if we choose to not add these two items, our capacity is still at 7 and the value of this empty

knapsack is obviously at 0. The full solution tree is given on the next page, and the inspection of the tree

leaves gives us the best solution.