1) (18 pts.) (i) Consider the following variation of the 0/1 Knapsack problem: G
ID: 3603256 • Letter: 1
Question
1) (18 pts.) (i) Consider the following variation of the 0/1 Knapsack problem: Given are a knapsack of capacity W and n items, with each item having a profit pi, a weight w, and a type ti, 1 SiSn. There are two types: G (gold) and S (silver). The objective is to fill the knapsack not exceeding its capacity W, maximizing the profit and achieving a balanced G/S ratio. A knapsack containing k S items has a balanced G/S ratio when the number of G items is at least k and at most 2k. Describe and analyze a DP algorithm for determining the items to pack resulting in a maximum profit and fulfilling the above constraints. Address that the principle of optimality holds. State and explain the DP equations and how the entries are computed, and how the items achieving maximum profit are generated from the computed entries. Analyze time and space. (ii) You are given an integer n. Starting at 1, you are asked to generate n using the following two operations: Plusl, which increases a given number by 1, and Double2, which doubles a given number. The cost of Plusl is 1 and the cost of Double2 is 2. For exarnple, n = 21, can be generated using Plus1, Double2. Plusl, Double2. Double2, Plusl with a cost of 9. Give a DP solution generating n using operations Plusl and Double2 minimizing the total cost. Analyze your solution and explain whether it has polynomial running time.Explanation / Answer
// initializations
int i, j;
int[][] P = new int[N+1][W+1]; // p[i][j] is the best profit for items 0 to i and knapsack of size j.
int[][] s = new int[N+1][W+1]; // s keeps track of which items are selected
for (i = 0; i <= N; i++)
for(j = 0; j <= W; j++)
s[i][j] = 0;
// trivial cases
for (i = 0; i <= N; i++) P[i][0] = 0; // no items left
for (j = 0; j <= W; j++) P[0][j] = 0; // no space left in knapsack
// for each item i from 1 to N:
for (i = 1; i <= N; i++) {
// consider all knapsack sizes j from 1 to W:
for (j = 1; j <= W; j++) {
if (w[i-1] > j) {
// case 1: Item i (i-1 here due to 0-indexing) does not fit in j.
// the profit is thus the same as the best-so-far for j.
P[i][j] = P[i - 1][j];
} else {
// case 2: item i (i-1 here due to 0-indexing) does fit in j.
// decide whether using item i is profitable.
tmp = P[i - 1][j - w[i-1]] + p[i-1];
if (tmp > P[i-1][j]) {
P[i][j] = tmp;
s[i][j] = 1;
} else {
P[i][j] = P[i-1][j];
}
}
}
}
// S[N][W] now contains the max profit.
// this code outputs the subset of the N items that led to that profit.
j = W;
for (i = N; i>= 1; i--) {
if (keep[i][j] == 1) {
System.out.println(i);
j -= w[i-1];
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.