Skip to content

Instantly share code, notes, and snippets.

@remiomosowon
Last active August 29, 2015 14:03
Multi-dimensional Knapsack Problem (MKP)

Problem Statement

There is a list of 28 items to be packed in a container whose volume is 12 (in some unit) and which can accommodate a maximum weight of 12210 (in some unit). Each item has a certain volume, a weight and a price associated with it. The objective is to pack the items in the container such that they do not exceed the maximum volume or the maximum weight of the container while at the same time maximizing the total price of the items packed. The given weights of the items in the same unit as that of the container are 821, 1144, 634, 701, 291, 1702, 1633, 1086, 124, 718, 976, 1438, 910, 148, 1636, 237, 771, 604, 1078, 640, 1510, 741, 1358, 1682, 993, 99, 1068, 1669. The given volumes of the items in the same unit as that of the container are 0.8, 1, 0.7, 0.9, 0.9, 0.8, 0.7, 0.6, 0.6, 0.9, 0.6, 0.7, 1, 0.7, 0.9, 0.6, 0.9, 0.6, 0.6, 0.8, 1, 0.6, 0.9, 0.7, 0.7, 0.7, 0.8, 1. Finally, the given prices of the items are 118, 322, 166, 195, 100, 142, 100, 145, 100, 208, 100, 312, 198, 171, 117, 100, 329, 391, 100, 120, 188, 271, 334, 153, 130, 100, 154, 289.

It is assumed that the shapes of the objects being packed and their orientations are irrelevant. That is, we can pack 10 items each of volume 10 cubic meters in a container that has a volume of 100 cubic meters or above irrespective of their shapes. In other words, we assume all objects to be perfect cuboids.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment