33. Use the Backtracking algorithm for the 0-1 Knapsack problem (Algorithm 5.7) to maximize the profit for the following problem instance. Show the actions step by step. Pi i Pi Wi Wi 1 $20 2 10 2 $30 6 3 $35 7 5 W = 9 4 $12 3 4 5 $3 1 3
33. Use the Backtracking algorithm for the 0-1 Knapsack problem (Algorithm 5.7) to maximize the profit for the following problem instance. Show the actions step by step. Pi i Pi Wi Wi 1 $20 2 10 2 $30 6 3 $35 7 5 W = 9 4 $12 3 4 5 $3 1 3
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
please answer question #33 to answer the question.
please use (Algorithm 5.7) for the Backtracking Algorithm for the 0-1 Knapsack Problem
please use java language for coding java file
- should start with your Last Name, Like SmithClubApp, PetrowskiTravelLogApp, for your class
short paragraph should include-
please label the question with the answer as well
-description of the java file
-what it does?
-what is the input data? expected output, samples of both
Transcribed Image Text:33. Use the Backtracking algorithm for the 0-1 Knapsack problem (Algorithm
5.7) to maximize the profit for the following problem instance. Show the
actions step by step.
Pi
i
Pi
Wi
Wi
1
$20
2
10
2
$30
3
$35
7
5
W = 9
4
$12
3
4
5
$3
1
3
![Algorithm 5.7
The Backtracking Algorithm for the 0-1 Knapsack Problem
Problem: Let n items be given, where each item has a weight and a profit.
The weights and profits are positive integers. Furthermore, let a positive
integer W be given. Determine a set of items with maximum total profit,
under the constraint that the sum of their weights cannot exceed W.
Inputs: Positive integers n and W; arrays w and p, each indexed from 1
to n, and each containing positive integers sorted in nonincreasing order
according to the values of p[i]/w[i].
Outputs: an array bestset indexed from 1 to n, where the values of bestset[i]
is "yes" if the ith item is included in the optimal set and is "no" otherwise;
an integer maxprofit that is the maximum profit.
BACKTRACKING
void knapsack (index i,
1
int profit, int weight)
if (weight W && profit > maxprofit){\
}
maxprofit
numbest = i;
profit;
bestset include;
if (promising (i)){
include [i+1] = "yes";
This set is best
// so far.
// Set numbest to
// number of items
considered. Set
//bestset to this
// solution.
// Include w[i+1].
knapsack (i+1, profit + p[i+1], weight + w[i + 1]);
include [i+1]
=
"no";
knapsack (i+1, profit, weight);
// Do not include
// w[i + 1].
}
}
bool promising (index i)
{
index j, k;
int totweight;
float bound;
if (weight > W)
return false;
else{
j = i + 1;
bound profit;
totweight weight;
// Node is promising only
if we should expand to
its children. There must
be some capacity left for
// the children.
while (j <=n&& totweight + w[j] < = W){\
totweight totweight + w[j];
bound bound + p[j];
Grab as many items as
possible.
j++;
}
k = j;
if (k <=n)
bound = bound (Wtotweight) p[k]/w[k];
Use k for consistency
// with formula in text.
*
return bound > maxprofit;
// Grab fraction of kth
// item.
}
}](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F2d578ff0-205d-4ea0-ad2c-0dd7aa11c763%2F31db5ee0-e58f-4be3-ad03-01d08895a1ab%2Fbgib5k_processed.jpeg&w=3840&q=75)
Transcribed Image Text:Algorithm 5.7
The Backtracking Algorithm for the 0-1 Knapsack Problem
Problem: Let n items be given, where each item has a weight and a profit.
The weights and profits are positive integers. Furthermore, let a positive
integer W be given. Determine a set of items with maximum total profit,
under the constraint that the sum of their weights cannot exceed W.
Inputs: Positive integers n and W; arrays w and p, each indexed from 1
to n, and each containing positive integers sorted in nonincreasing order
according to the values of p[i]/w[i].
Outputs: an array bestset indexed from 1 to n, where the values of bestset[i]
is "yes" if the ith item is included in the optimal set and is "no" otherwise;
an integer maxprofit that is the maximum profit.
BACKTRACKING
void knapsack (index i,
1
int profit, int weight)
if (weight W && profit > maxprofit){\
}
maxprofit
numbest = i;
profit;
bestset include;
if (promising (i)){
include [i+1] = "yes";
This set is best
// so far.
// Set numbest to
// number of items
considered. Set
//bestset to this
// solution.
// Include w[i+1].
knapsack (i+1, profit + p[i+1], weight + w[i + 1]);
include [i+1]
=
"no";
knapsack (i+1, profit, weight);
// Do not include
// w[i + 1].
}
}
bool promising (index i)
{
index j, k;
int totweight;
float bound;
if (weight > W)
return false;
else{
j = i + 1;
bound profit;
totweight weight;
// Node is promising only
if we should expand to
its children. There must
be some capacity left for
// the children.
while (j <=n&& totweight + w[j] < = W){\
totweight totweight + w[j];
bound bound + p[j];
Grab as many items as
possible.
j++;
}
k = j;
if (k <=n)
bound = bound (Wtotweight) p[k]/w[k];
Use k for consistency
// with formula in text.
*
return bound > maxprofit;
// Grab fraction of kth
// item.
}
}
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education