Home | | User Interface Design | Knapsack Problem or Rucksack Problem

Chapter: Analysis and Design of Algorithm : Divide and Conquer, Greedy Method

Knapsack Problem or Rucksack Problem

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than a given limit and the total value is as large as possible.

KNAPSACK PROBLEM

 

 

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.

 

The problem often arises in resource allocation with financial constraints. A similar problem also appears in combinatorics, complexity theory, cryptography and applied mathematics.

 

The decision problem form of the knapsack problem is the question "can a value of at least V be achieved without exceeding the weight W?"

 

E.g.

 

A thief enters a store and sees the following items:

 

His Knapsack holds 4 pounds.

 

What should he steal to maximize profit?

 

 

Fractional Knapsack Problem

 

Thief can take a fraction of an item.

 



GREEDY TECHNIQUES

 

The greedy approach suggests constructing a solution through a sequence of steps, each expanding a partially constructed solution obtained so far, until a complete solution to the problem is reached. On each step—and this is the central point of this technique—the choice made must be

        Feasible, i.e., it has to satisfy the problem‘s constraints.

 

        Locally optimal, i.e., it has to be the best local choice among all feasible choices available on that step.

 

        Irrevocable, i.e., once made, it cannot be changed on subsequent steps of the algorithm.

 


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Analysis and Design of Algorithm : Divide and Conquer, Greedy Method : Knapsack Problem or Rucksack Problem |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.