The knapsack problem (often called the zero-one knapsack problem) is as follows:
ID: 3778048 • Letter: T
Question
The knapsack problem (often called the zero-one knapsack problem) is as follows: given n rods of length 8_1, 8_2, ..., 8_n and a natural number S, find a subset of the rods that has total length exactly S. The standard dynamic programming algorithm for the knapsack problem is as follows. Let t[I, j] be true if there is a subset of the first i items that has total length exactly j. function knapsack(8_1, 8_2, ..., 8_n, S) t[0, 0]: = true for j:= 1 to S do t[0, j]: = false for i:= 1 ton do for j:= 0 to S do t[i, j]:=t[i-l, j] if j - 8_1 greaterthanorequalto 0 then t[I, j]:= t[i, j] V t[I -1, j - 8_1] return(t[n, S]) Fill in the table t in the dynamic programming algorithm for the knapsack problem on a knapsack of size 19 with rods of the following lengths: 15, 5, 16, 7, 1.15, 6, 3.Explanation / Answer
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0
1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0
1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 1 1 1 0
1 1 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
=====
where 1 = true and 0=false
The c program is given below:
# include<stdio.h>
int knapsack(int* p, int n, int s) {
bool t[100][100];
t[0][0]=true;
for(int j=1; j<=s; j++) {
t[0][j]=false;
for(int i=1; i<=n; i++) {
for(j=0;j<=s;j++) {
t[i][j]=t[i-1][j];
if(j-p[i] >= 0) {
t[i][j]=t[i][j]|t[i-1][j-p[i]];
}
}
}
}
for(int i=0; i<n; i++) {
for(int k=0; k<s; k++) {
printf("%d ",t[i][k]);
}
printf(" ");
}
return 1;
}
int main() {
int p[8] = {15,5,16,7,1,15,6,3};
knapsack(p,8,19);
return(0);
}
=====
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.