2023年11月25日

Java代写 | CSI 2120 Programming Paradigm

本次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.