Algorithm 5.7The Backtracking Algorithm for the 0-1 Knapsack ProblemProblem: Let n items be given, where each item has a weight and a profit.The weights and profits are positive integers. Furthermore, let a positiveinteger 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 1to n, and each containing positive integers sorted in nonincreasing orderaccording 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.BACKTRACKINGvoid knapsack (index i,1int profit, int weight)if (weight W && profit > maxprofit){\}maxprofitnumbest = i;profit;bestset include;if (promising (i)){include [i+1] = "yes";This set is best// so far.// Set numbest to// number of itemsconsidered. 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 onlyif we should expand toits children. There mustbe 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 aspossible.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.}} 33. Use the Backtracking algorithm for the 0-1 Knapsack problem (Algorithm5.7) to maximize the profit for the following problem instance. Show theactions step by step.PiiPiWiWi1$202102$303$3575W = 94$12345$313

The 0-1 Knapsack problem is a classic combinatorial optimization problem in computer science and…

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 $30 25 10 6 3 $35 7 5 W = 9 4 $12 3 4 5 $3 1 3

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 $30 25 10 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

See similar textbooks

Related questions

Q: Write a C program to solve the fractional knapsack problem. For example, the weights and values of 3…

A: Here is the c program. I have provided source code screenshot in the below steps. See below steps…

Q: In Python describe a Naive Bayes model for predicting whether the game should be played based on the…

A: Import Required Libraries:1from collections import defaultdict 2import numpy as npThe code begins by…

Q: Apply the rod cutting dynamic programming algorithm to the following example:

A: C++ code for rod cutting dynamic programming algorithm #include…

Q: Ten times out of ten, a coin will always land on its head. In how many cases are there four…

A: Divide arithmetic and probability Theory form the spinal column of processor discipline. These…

Q: Write program that simulates the toss of a six sides die. What is the ratio of the number 2 with the…

A: Dear Student, Here, Input will be the number of times you want to toss the die. Output will be the…

Q: Given the following regular expression: 1. r = 01*(34) 2. r=1*(34)*0 3. r= (1|(23)* )0 4. r =…

A: Given regular expressions can be rewritten by using + and * regular expression symbols as follows,…

Q: Find the best solution for the 0-1 knapsack problem using backtracking algorithm. We have 5 items…

A: The above question is solved in step 2 and step 3 :-

Question

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.
}
}

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

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

SEE SOLUTION Check out a sample Q&A here

Step 1: To solve the 0-1 Knapsack problem using the Backtracking algorithm:-

VIEW

Step 2: Let's perform the Backtracking algorithm step by step:

VIEW

Step 3: Step 4- Move to the next item (currentIndex = 1)

VIEW

Step 4: Step 9- Move to the next item (currentIndex = 4)

VIEW

Solution

VIEW

Step by step

Solved in 5 steps

SEE SOLUTION Check out a sample Q&A here

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.

Similar questions

Find the best solution for the 0-1 knapsack problem using backtracking algorithm. We have 5 items with price and weight: $50 $30 $40 $100 $20 10 1. 2. 3. 2 4. 10 5. 5 Limitation on the weight is: W = 21
Design a dynamic programming algorithm for the following problem. Find the maximum total sale price that can be obtained by cutting a rod of $n$ units long into integer-length pieces if the sale price of a piece $i$ units long is $p_i$ for $i = 1, 2, . . . , n$. What are the time and space efficiencies of your algorithm?
The following loop has multiple types of dependences. Find all the true dependences, output depende- nces and anti dependences and eliminate the output dependences by renaming. For( i = 1; i<= 100; i = i+1) { Y[i] = X[i]/C; %3D X[i] = X[i] + C; %3D Z[i] = Y[i] + C; %3D Y[i] = C-Y[i]; %3D
X-Kingdom has trapped n number of soldiers of their opponent. They want to execute them. They created a strategy so that the prisoners will kill each other and at the end one prisoner will be alive and eventually released. As part of the process, they assigned each trapped soldier a sequence number starting from 1 and ending at n. If n = 5 and k = 2, then the safe position is 3. Firstly, the person at position 2 is killed, then person at position 4 is killed, then person at position 1 is killed. Finally, the person at position 5 is killed. So, the person at position 3 survives. If n = 7 and k = 3, then the safe position is 4. The people at positions 3, 6, 2, 7, 5, 1 are killed in order, and the person at position 4 survives. Input:n and k Output:Print the list of prisoners in reverse order from n to 1Then reverse the list to print it in correct order from 1 to nDisplay the position number who will survive. You must have to use circular doubly linked list for your solution. You…
In a hypothetical study of population dynamics, scientists have been tracking the number of rabbits and foxes on an island. The number of rabbits and foxes are determined once a year using high resolution infrared cameras and advanced computer vision methods.Each year, the number of rabbits and foxes are found to change by the following equations: $$ {\Delta}R = round( kr*R - krf*R*F ) $$ $$ {\Delta}F = round( -kf*F + kfr*R*F ) $$ where $ {\Delta}r $ and $ {\Delta} f $ are the changes in number of rabbits and foxes by the end of that year; and R and F are the population sizes at the end of the previous year. kr, krf, kf, kfr are coefficients that depend on the species of rabbits and foxes.With these dynamics, the scientists realize that one or both species can become extinct on the island. At the end of each year, if there are fewer than 2 animals of a kind, the scientists transfer rabbits and/or foxes to make sure there are at least 2 of each kind.Write a function…
An object leaves point P1 with coordinates (−1,0) and travels with velocity v1=1 in a straight line to point P2 with coordinates (0,h) . It then travels with velocity v2=2 in a straight line from P2 to point P3 with coordinates (x , y ). Given x and y values there will be some optimal h value that minimizes the total travel time. Write a program in Scilab containing a function in the form function u = h(x,y) [your code goes here] endfunction u = h(1,2); disp(u); that calculates this optimal h value (to an accuracy of about 10^−6 ) given x and y values as arguments. Your function must work for any positive values of x and y.