Define the knapsack problem

Assignment Help Basic Computer Science

Reference no: EM131312684

The knapsack problem is a classic problem in computer science. You are given a knapsack and a collection of items of different weights and your job is to try to fit some combination of the items into the knapsack to obtain a target weight. All of the items do not have to fit in the knapsack, but the total weight cannot exceed the target weight. For example, suppose we want to fill the knapsack to a maximum weight of 30 pounds from a collection of seven items where the weights of the seven items are 2, 5, 6, 9, 12, 14, and 20. For a small number of items, it's rather easy to solve this problem. One such solution, for example, would be to include the items that have weights 2, 5, 9, and 14. But what if we had several thousand items of varying weights and need to fit them within a large knapsack? Design and implement a recursive algorithm for solving this problem.

Reference no: EM131312684

Questions Cloud

Design and implement a program that prints pascal''s triangle : Design and implement a program that prints Pascal's triangle

Describe the dba responsibilities : Describe the DBA's responsibilities. How can the DBA function be placed within the organization chart? What effect(s) will such placement have on the DBA function?

Describe the two different types of wlan modes : 1. Describe the two different types of WLAN Modes and list their components. What are the drawbacks and limitations of each? 2. Describe the two different types of WLAN Modes and list their components.

What is the effective length of the bolt : Define prying action? Sketch an alternative joint diagram showing the effects of prying action Name at least two things the joint designer can do to reduce prying action?

Define the knapsack problem : One such solution, for example, would be to include the items that have weights 2, 5, 9, and 14. But what if we had several thousand items of varying weights and need to fit them within a large knapsack? Design and implement a recursive algorithm ..

Impact of various internal and external organizational : Impact of Various Internal and External Organizational "Environments" on IT Management - Your Capstone Case assignment is to produce a reasonable and workable plan to set the stage for these forthcoming IT improvements-a plan that will help affecte..

Summarize two key information security practices : Summarize two key information security practices you recommend the company implement. Provide supporting examples/research/justification using a real-world example (e.g., when a real company was hacked and what the outcomes were).

What is stiffness of the bolt and the stiffness of the joint : What is the stiffness of the bolt and the stiffness of the joint?- What is the resilience of the bolt and of the joint members?

Explain javascript features implemented throughout the pages : Explain At least 5 JavaScript features implemented throughout the pages, At least 1 PHP features implemented throughout the pages, At least 1 JavaScript or PHP feature not covered in class and From one of the chapters not covered.

User Account

All Pages