Apply the dynamic programming algorithm discussed in Chapter 7 to fill the given table for a knapsack instance of 7 items having values 10, 5, 15, 7, 6, 18, 3 and sizes 2, 3, 5, 7, 1, 4, 1. The knapsack capacity is C =13. The first row and the first column are already filled. The value of the optimal solution is also given.

Apply the dynamic programming algorithm discussed in Chapter 7 to fill the given table for a knapsack instance of 7 items having values 10, 5, 15, 7, 6, 18, 3 and sizes 2, 3, 5, 7, 1, 4, 1. The knapsack capacity is C =13. The first row and the first column are already filled. The value of the optimal solution is also given.

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: It is Halloween again, and trick or treat is around the corner. You have the following problem to…

A: Answer: We have explain the algorithm of the given program and we have discussed about the time and…

Q: If it is possible to construct an optimal solution for a problem by constructing optimal solutions…

A: The dynamic programming technique works by solving the subproblems in a bottom-up fashion, starting…

Q: Given a collection of n shapes on the plane, a valid traversal from shape A to shape B is a sequence…

A: The problem at hand involves finding the minimum cost traversal from shape A to shape B in a…

Q: An Integer knapsack problem with 6 items is provided to you, you need to find the maximum benefit…

A: Given a Knap sack problem, It contains 6 items and each contains it's own weight and profit. The…

Q: In an optimal A* search, a- describe the problem of a heuristic function that overestimates the…

A: A* maintains a list of options it's considering, ordered by how good they might be. It keeps looking…

Q: Consider the following search problem, represented as a graph. The start state is S and the only…

A: The answer for the given questions are as follows.

Q: Use the greedy algorithm below to solve the activity problem. Suppose the S={a,a.....an) is a set of…

A: Greedy seems to be a computational technique that develops a solution layer by layer, always…

Q: max ₁ + 2x₂ + 5x3 subject to -x₁ + x₂ + 3x3 0 X3 ≥ 0.

A: You can use the Julia programming language with the JuMP (Julia for Mathematical Programming)…

Q: The gradient descent algorithm may get stuck in a local optimal point because the gradient is near…

A: Gradient Descent Algorithm:- A gradient descent algorithm is an optimization technique used to find…

Q: A school is creating class schedules for its students. The students submit their requested courses…

A: In the above problem where we need to find the optimal schedule for all the students, this is a type…

Q: An algorithm A is admissible if (a) It is not guaranteed to return an optimal solution when one…

A: Question. An algorithm A is admissible if (a) It is not guaranteed to return an optimal solution…

Q: Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose…

A: For 14: NoFor 6: NoFor 10: NoFor 100: Yes

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 :-

Q: A bottom up dynamic programming method is to be used to solve the subset sum problem. The problem is…

A: This query relates to dynamic programming. The subset sum problem is to be solved through bottom up…

Q: an optimal solution to a problem can be obtained by greedy, It can also be obtained by dynamic…

A: Please find the answer below :

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

A: Backtracking can be used to solve the knapsack problem as shown below: Resource allocation issues…

Q: Insufficient Overlapping Subproblems and the Principle of Optimality (Optimal Substructure) are both…

A: In this question we have to understand and discuss the concepts of "Insufficient Overlapping…

Q: 8. A school is creating class schedules for its students. The students submit their requested…

A: As per the given problem, the most optimal schedules need to be found out. Finding the exact…

Question

A. Apply the dynamic programming algorithm discussed in Chapter 7 to fill the given table for a
knapsack instance of 7 items having values 10, 5, 15, 7, 6, 18, 3 and sizes 2, 3, 5, 7, 1, 4, 1.
The knapsack capacity is C=13. The first row and the first column are already filled. The
value of the optimal solution is also given.
0<j<C=13
0.
1
3 4 5 6 7
8 9
10 11
12
13
00 0000 0000 00
Vi=10, S-2 1 0
V=5, S2=3
2 0
V3=15, S3=5 3 0
V4=7, S4=7
40
Vs=6, Ss=1
50
V-18, S6-4 6 0
V-3, S7=1
70
52
B. A way to find the items forming an optimal solution is to sort the items in decreasing order
according to
where Vi and S; are the value and the size of item i. If there is a sequence of
successive items starting from the item 1 where their total size is equal to C (The knapsack
capacity), then they form an optimal solution. Use this method to find and optimal solution
(indicate its items, total value and total size).

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!

SEE SOLUTION Check out a sample Q&A here

Step 1

Step 2

Step 3

Step 4

Trending now

This is a popular solution!

Step by step

Solved in 4 steps with 7 images

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

A student has been asked to put some parcels on a shelf. The parcels all weigh different amounts, and the shelf has a maximum safe loading weight capacity of 150 Kg. The weight of parcels are as follows (in Kg): The student has been asked to load the maximum weight possible parcels on the shelf subject to the maximum safe loading weight. State two possible approaches for a greedy algorithm solution to solve this problem. In each case, state clearly the result you would get from applying that approach to this problem, stating whether the solution is optimal or not. If your answer does not produce an optimal solution, what algorithm could be employed to find one?
Both the Principle of Optimality (Optimal Substructure) and Insufficient Overlapping Subproblems are valid inputs for dynamic programming. To see how difficult it is to meet these two criteria, consider the case of All-Pairs Shortest Paths.
Give a brief description in the given image attached
5.1. Trace the operation of Greedy Best-First Search, applied to the problem of getting to the goal state G from state S given below, for the following heuristic function: h,(N) = sum of the (Manhattan) distances of every tile to its goal position 341 25 876 State S 432 16 578 State G
The monotone restriction (MR) on the heuristic function is defined as h (nj ) 2 h (ni ) - c (ni , nj ). Please prove the following: 1. If h(n)
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.