Week 7 Discussion Forum

Knapsack Problem

Knapsack Problem

by MD.TORIKUL ISLAM ( 192-15-2852 ) EMON -
Number of replies: 1

That is a famous Dynamic Programming Problem that falls in the optimization category.

It derives mainly its name from a scenario where, it is given a set of items with specific weights and assigned values, that goal is to maximize the value in a knapsack while remaining within the weight constraint.

Each and every item can only be selected once as we do not have multiple quantities of any items.

70 words

In reply to MD.TORIKUL ISLAM ( 192-15-2852 ) EMON

Re: Knapsack Problem

by Md. Sabbir Hossain 192-15-2809 -
0/1 Knapsack Problem Using Dynamic Programming-
Consider:
  • Knapsack weight capacity = w
  • Number of items each having some weight and value = n

Time Complexity-
  • Each entry of the table requires constant time θ(1) for its computation.
  • It takes θ(nw) time to fill (n+1)(w+1) table entries.
  • It takes θ(n) time for tracing the solution since tracing process traces the n rows.
  • Thus, overall θ(nw) time is taken to solve 0/1 knapsack problem using dynamic programming.

79 words