A bottom up dynamic programming method is to be used to solve the subset sum problem. The problem is to find the optimal sum of weighted requests from a set of requests ? subject to a weight constraint W. The set of weighted requests ? = {?1, ?2, ?3, ?4, ?5, ?6} can be summarised as following: SubsetSum(n, W):Let B(0, w) = 0 for each w = {0,..., W}for i=1 to nfor w+ 0 to Wif w< w; thenB(i, w) B(i - 1, w)←elseB(i, w)max (w; + B(i-1, w - w;), B(i - 1,w))(a) Produce a table showing the space of the problem and all of the subproblems, and use that table to determine the optimal subset sum ofrequests when the weight constraint of 13 is applied. The table shouldtake the form of a matrix with 7 rows (values of i in the range 0 to 6inclusive) and 14 columns (values of w in the range 0 to 13 inclusive). Requestα1α2α3α4α5α6The maximum weight constraint is 13.w(α₁)221771

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

Answered: A bottom up dynamic programming method…

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

Question

100%

A bottom up dynamic programming method is to be used to solve the subset sum problem. The problem is to find the optimal sum of weighted requests from a set of requests ? subject to a weight constraint W. The set of weighted requests ? = {?1, ?2, ?3, ?4, ?5, ?6} can be summarised as following:

SubsetSum(n, W):
Let B(0, w) = 0 for each w = {0,..., W}
for i=1 to n
for w+ 0 to W
if w< w; then
B(i, w) B(i - 1, w)
←
else
B(i, w)
max (w; + B(i-1, w - w;), B(i - 1,w))
(a) Produce a table showing the space of the problem and all of the sub
problems, and use that table to determine the optimal subset sum of
requests when the weight constraint of 13 is applied. The table should
take the form of a matrix with 7 rows (values of i in the range 0 to 6
inclusive) and 14 columns (values of w in the range 0 to 13 inclusive).

Request
α1
α2
α3
α4
α5
α6
The maximum weight constraint is 13.
w(α₁)
2
2
1
7
7
1

Expert Solution

Step by step

Solved in 3 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