A (short) variation of Bin Packing with small dimensions.

Правка en1, от FoolForCS, 2017-11-04 09:52:51

Problem Statement:

There are K containers each with a capacity vector defined in three dimensions as (X[i], Y[i], Z[i]), 1 <= i <= 3, 1 <= K <= 15. When an object of capacity (a, b, c) is put into container of capacity (A, B, C), the containers remaining capacity becomes (A — a, B — b, C — c). There are N objects of varying capcities to be put into containers. Determine if the all objects can be fit into the containers or not. If they can fit, also determine which object must be put in which container. (1 <= N <= 150). The capacity ranges fit an integer.

An exact solution would be amazing, but a good heuristic that might be able to solve this problem reasonably well is much appreciated. Any ideas?

Теги bruteforce, np-hard, dp?, greedy

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский FoolForCS 2017-11-04 09:58:58 9 Tiny change: '1 <= i <= 3, 1 <= K <' -> '1 <= i <= 15, i.e., 1 <= K <'
en2 Английский FoolForCS 2017-11-04 09:57:50 60 Tiny change: '_#### Problem St' -> '### _Problem St' (published)
en1 Английский FoolForCS 2017-11-04 09:52:51 827 Initial revision (saved to drafts)