# 本次加拿大CS代写主要是函数式编程相关使用Scheme/Prolog实现背包问题算法求解

Comprehensive Assignment (32%)

CSI 2120 Programming Paradigm Winter 2021
Part 1 due on Januaray 25 at 23:00
Part 2 due on February 22 at 23:00
Part 3 & 4 dues on April 14 at 23:00

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
< ?0,?1,?2,…,??−1 > and < ?0,?1,?2,…,??−1 >

and a number W > 0, find the subset K ⸦ {0,1,…,n-1} that maximizes

subject to

∑?? ?∊?

∑?? ≤? ?∊?

CSI 2120 page 2 _________________________________________________________________________________________________

Example:

Consider the following example with a knapsack of capacity 7:

The solution to this problem is to select items B and D for a total value of 21 and a total weight of 7.

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.

 Item A Item B Item C Item D Value 1 6 10 15 Weight 1 2 3 5

CSI 2120 page 3 _________________________________________________________________________________________________

Few observations about the knapsack solution tree:

• this is a perfect tree with a height equals to the number of items;
• some nodes of the tree can correspond to infeasible solutions when the knapsack capacitybecomes negative, in that case there is no need to explore the subtree below;
• the number of nodes of this tree is 2n+1-1 which means that the complexity of the brute algorithmfor n items is O(2n). Consequently, this approach becomes rapidly impracticable when the

number of items becomes large.

We therefore need a better algorithm to solve this problem in the general case.