Write down the algorithm for greedy strategies for the Knapsack problem.
Subject Algorithm Design
NU Year Set: 2.(a) Marks: 5 Year: 2008

Knapsack Problem

Given a set of items, each with a weight and a value, determine a subset of items to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

The knapsack problem is in combinatorial optimization problem. It appears as a subproblem in many, more complex mathematical models of real-world problems. One general approach to difficult problems is to identify the most restrictive constraint, ignore the others, solve a knapsack problem, and somehow adjust the solution to satisfy the ignored constraints.

Applications

In many cases of resource allocation along with some constraint, the problem can be derived in a similar way of Knapsack problem. Following is a set of example.

  • Finding the least wasteful way to cut raw materials
  • portfolio optimization
  • Cutting stock problems

 

Login to post your comment.