How many different optimal subsets does the instance have

Assignment Help Basic Computer Science

Reference no: EM131125354

a. Apply the dynamic programming algorithm to the following instance of the 0-1 knapsack problem:

Item	Weight	Value
1	3	$25
2	2	$20
3	1	$15
4	4	$40
5	5	$50

capacity W = 6. Show your pseudo codes for the dynamic programming solution. You should include a procedure to retrieve an optimal solution.

b. How many different optimal subsets does the instance of part (a) have?

c. In general, how can we use the table generated by the dynamic programming algorithm to tell whether there is more than one optimal subset for the knapsack problem's instance?

Reference no: EM131125354

Questions Cloud

Gallatin hardware is a small hardware store : Gallatin Hardware is a small hardware store in the rural township of Willow Creek that rarely extends credit to its customers in the form of an account receivable.

Write a c program that reads several different name : This union should itself contain two structures, one for baseball-related statistics and the other for football-related statistics. Test the program using a current set of league statistics. (Ideally, the program should be tested using both baseba..

First calendar quarter to consider three projects : Your company Portfolio Manager is convening a review board in the first calendar quarter to consider three projects. You have been asked to provide recommendations with respect to the capital budgeting aspects of these projects.

Discuss three major concerns of public budgeting : From the first e-Activity, discuss three major concerns of public budgeting and finance for a public administrator. Justify your response with examples.

How many different optimal subsets does the instance have : In general, how can we use the table generated by the dynamic programming algorithm to tell whether there is more than one optimal subset for the knapsack problem's instance?

In what section of the balance sheet should a note : In what section of the balance sheet should a note receivable be listed if its term is (a) 90 days, (b) six years?

Analyze the broad range of talent management efforts : Describe and analyze the broad range of talent management efforts that use software applications to help you Director to make an educated decision.

Determine the number of days sales in inventory : Determine the number of days' sales in inventory and inventory turnover for the three companies. Round to the nearest day and one decimal place.

Generated a forecast for the next eight weeks : Spring and Summer Fashions, a clothing producer, has generated a forecast for the next eight weeks. Demand is expected to be fairly steady, except for periods 3 and 4, which have higher demands:

User Account

All Pages