knapsack problem

Question: You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount OR S), find the minimum number of coins required to get the exact amount. Problem statement “Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way that they sum up to S. [Read More]

Problem Statement 0-1 Knapsack problem Input : There are n items, and each item has a value: value vi (non negative) size or weight wi (non negative and integral ) Capicity W (non negative and integer) Output: Select a subset S ⊆ {1,2,3,….n} that maximizes ∑ vi  subject to max value&sum wi ≤ W  Sometimes you may hear a cheesy problem a thief robbing a store and can carry a maximal weight of W into their knapsack. [Read More]