本次Java代写是通过编程解决数学问题

CSI 2120 Programming Paradigm

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.

2. Dynamic programming

In this approach we will iteratively solve our knapsack problem by solving each sub-problem until we

obtain the full solution. That is if the capacity of the knapsack is W then we will solve the problem for

knapsacks of capacity 0, 1, 2, … up to W with numbers of items going from 0 to n. We will proceed by

building a table that will list all these subproblems.

Let’s first consider the obvious cases: that is when the knapsack has a capacity of 0 and also the ones

where we have 0 item to add to the knapsack. We use here the example presented earlier. The columns

of this table correspond to knapsacks of capacity 0 to n (here n=7). The rows correspond to the case

where we consider 0 to n items (i.e. first row is for 0 item, second row is for item A only, third row is for

the sub-problems where we only have items A and B, etc). The cells of this table give us the solution

(maximum value) for each corresponding sub-problem. The solution to the problem we want to solve

will be found in the bottom right cell.

As it can be seen in the first column of the table below, the solution for knapsacks of capacity 0 has

always a value of 0 (obviously) no matter how many items we have. Same for the first row where the

solution is also 0 when there is no item to put in the knapsack.

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** [email protected] **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。