### Problem :

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. (Reference :wiki)

Here is a simpler view of the problem : Consider a thief gets into a home to rob and he carries a knapsack. There are fixed number of items in the home – each with its own weight and value – Jewellery, with less weight and highest value vs tables, with less value but a lot heavy. To add fuel to the fire, the thief has an old knapsack which has limited capacity. Obviously, he can’t split the table into half or jewellery into 3/4ths. He either takes it or leaves it.

### Java implementation :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | package com.topjavatutorial; public class KnapsackAlgorithm { public static void main(String[] args) { int[] value = { 10, 50, 70 }; // Values of items int[] weight = { 10, 20, 30 }; // Weight of items int capacity = 40; // Knapsack Max weight int itemsCount = 3; int result = KnapSack(capacity, weight, value, itemsCount); System.out.println(result); } public static int KnapSack(int capacity, int[] weight, int[] value, int itemsCount) { int[][] K = new int[itemsCount + 1] [capacity + 1]; for (int i = 0; i <= itemsCount; ++i) { for (int w = 0; w <= capacity; ++w) { if (i == 0 || w == 0) K[i][w] = 0; else if (weight[i - 1] <= w) K[i][w] = Math.max((value[i - 1] + K[i - 1] [w - weight[i - 1]]), K[i - 1][w]); else K[i][w] = K[i - 1] [w]; } } return K[itemsCount] [capacity]; } } |

#### Output :

80

© 2017, www.topjavatutorial.com. All rights reserved. On republishing this post, you must provide link to original post