Optimal subset for the knapsack problems instance

Assignment Help Data Structure & Algorithms

Reference no: EM131145439

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

Questions Cloud

How you would conduct simulation to perform risk analysis : Choose any industry and describe how you would conduct a simulation to perform risk analysis.

Discuss the differences in the benefits to farmers : uppose the government wants to increase the price of a specific agricultural product.Discuss the welfare effects of four possible policies: price floor, price support, production quotaand voluntary production reduction. Which policy is least effici..

Developing leaders for a sustainable global society : Which design will you choose?- Would it make a difference in your decision if the design was primarily for economically-developed countries or for third-world countries?

What do you think of this idea : ValuMart, a large national retail chain, is nearing its fiscal year-end. It appears that the company is not going to hit its revenue and net income targets.

Optimal subset for the knapsack problems instance : 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?

Strategic action plan outline : Strategic Action Plan Outline. Cover page (does not count toward your final page count) ?Overview of Organization and Sector (suggested length: 1 page) ?Forces for change. ?Degree of uncertainty and turbulence. Define framing of power. ?Define the g..

A. how many spaghetti dinners should the firm make each day : a. How many spaghetti dinners should the firm make each day? b. What if the firm has avoidable fixed costs of $1562.50? c. What is the firm's supply function if there is no avoidable fixed cost? d. What is the supply function if the firm has avoidabl..

Which economic systems would be most suitable for a country : Which economic systems would be most suitable for a country: centrally planned, mixed economy, or market economy? Since Canada is the #1 trading partner with the USA, focus specifically on Canada.

Explain in terms of the environmental kuznets curve : Explain in terms of the environmental Kuznets curve.

User Account

All Pages