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: play out the activity: select two diverse lists i,j (1≤i,j≤n, i≠j) and two integers x,y…

A: Here have to determine about make the exhibit problem statement.

Q: Write a program in python to get the lossing probability after taking the winning probability from…

A: The sum of probabilities of winning and loosing is 1 So here we use the same logic to find the…

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: The primary purpose or function of a data warehouse is: Group of answer choices Transaction…

A: The data warehouse is actually a large collection of data that collects or gathers the data for…

Q: Write a program that graphs the equation {Using Matlab only}

A: The required Matlab code using the plot function has been provided in the next step.

Q: 1. Encode the problem and create an initial population of 4 different chromosomes 2. Explain what…

Q: Polycarp is altering a convoluted PC program. To begin with, factor x is pronounced and alloted to…

A: Here have to determine about the Forbidden Value programming problem statement.

Q: In java and given the following points in a plane(x1,y1) through (x5,y5): (1,3), (2,5), (3,7),…

A: To solve this problem using LPSolve in Java, we first need to define the decision variables,…

Q: particular integers x1,x2,… ,xn are composed on the board. Nezzar can play out the accompanying…

A: Here have to determine about the Nezzar can play out programming problem statement.

Q: Suppose that you pick number a from the principal pack and number b from the subsequent sack. Then,…

A: Here have to determine about the principal pack and number programming problem statement.

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: For a given state s and 5 actions (a,b,c,d,e), we have 5 Q-values: Q(s,a): 11.3 Q(s,b): 4.7 Q(s,c):…

A: Utility value - This is the value assigned to the actions performed in AI. This is assigned by…

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: Using Knapsac algorithm, solve the problem. Following are the list of items, and the size of Knapsac…

A: We will solve this by greedy method.. item carrot Radish cucumber Beans cauliflower Okra Potatoes…

Q: service (SaaS

A: Software as a service (SaaS) is a software authorizing and conveyance model in which software is…

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

Python Big-O Notation Pls answer only if u know Big-O What is the worst case auxiliary space complexity of bar(x,y)?
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.
c program Implement 0/1 Knapsack problem using dynamic programming and show the following output. .OUTPUT:enter the number of items4enter the weight and profit of the item 1:2 12enter the weight and profit of the item 2:1 10enter the weight and profit of the item 3:3 20enter the weight and profit of the item 4:2 15enter the capacity of the knapsack: 5The maximum profit is 37The most valuable subset is :{ item 4, item 2, item 1 }