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 |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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