Java Algorithms The skeleton code below is the start of a program to solve the 0
ID: 3739335 • Letter: J
Question
Java Algorithms
The skeleton code below is the start of a program to solve the 0-1 knapsack problem (p425 in CLRS, and lecture notes): Given n objects, each with integer weight wi and price pi , and a knapsack that can hold up to weight W, select the most valuable subset of objects that don’t exceed the knapsack’s capacity. All weights and prices will be positive integers. Implement a dynamic programming solution to the problem.
For this assignment, you will implement the FindDynamic method (and any helper methods you want) in LAB8.java. In addition to returning an array with the included items, you should also update the class variable best price with the optimal price in a solution.
There are two algorithms already implemented:
findEnumerate Tests every possible subset for the weight limit and price of the knapsack.
findGreedy Greedily picks the best remaining item based on its price:weight ratio, which is sometimes suboptimal.
The item files are supplied in the objects directory. They are text files with a (weight price) pair to describe an item on each line.
Below the code are sample text files
Large 1
349 5
833 187
684 201
309 452
471 691
680 675
96 794
246 559
872 837
219 855
720 17
253 922
658 258
911 21
941 357
569 754
964 957
480 337
301 151
991 616
Large 2
20 11
17 19
6 11
13 24
14 31
16 31
14 26
3 37
9 39
5 35
6 19
3 24
14 19
14 37
5 38
14 23
1 34
7 15
3 26
19 33
5 12
9 13
10 12
3 14
20 11
11 27
8 19
1 10
18 23
3 15
17 28
11 30
5 34
18 39
4 25
11 10
15 40
18 17
6 15
17 17
17 16
10 19
14 24
5 22
13 30
5 24
10 19
3 12
10 34
3 10
18 33
11 18
1 26
4 32
9 35
7 17
14 16
7 18
5 38
8 35
16 37
10 38
19 19
1 16
3 15
4 31
13 32
1 37
12 18
18 11
12 25
16 31
3 32
12 38
5 12
1 35
20 31
18 40
17 28
17 10
20 10
8 32
16 20
10 35
7 34
15 31
4 35
9 10
3 15
1 35
20 29
9 21
7 30
5 15
10 28
19 12
5 25
10 30
19 25
3 27
Small 1
12 24
7 13
11 23
8 15
9 16
Small 2
4 18
2 8
2 10
1 7
3 12
4 11
2 6
2 11
1 4
3 12
Tiny
1 3
2 5
2 4
3 7
Explanation / Answer
for (int w = 0; w <= weight; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = (table[i-1].price + K[i-1][w-wt[i-1]] > K[i-1][w] ? table[i-1].price + K[i-1][w-wt[i-1]] : K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.