Refer My Notes

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 or equal to a given limit and the total value is as large as possible Given a knapsack of capacity m and number of items n of weight w1, w2, w3 ... , wn with profits p1, p2, p3..., pn. Let x1,x2,...,xn is an array that represents the items has been selected or not. If the item i is selected, then xi = 1 If the item i is not selected then x i = 0 In 0/1 knapsack, the item can be selected or completely rejected. The items are not allowed to be broken into smaller parts. The main objective is to place the items into the knapsack so that maximum profit is obtained or find the most valuable subset of items that fits into the knapsack. Constraints: The weight of the items chosen should not exceed the capacity of knapsack. Obj...