三维背包问题怎么解决

Question

3D Knapsack
描述
你有一个三维背包，尺寸为 n,m,p（长×宽×高，单位是格子）。
同时有 q个物品，每个物品有长wi、宽hi、高di 和价值ci。
物品可以任意旋转（即长宽高可以互换），但不能切割，且放入时必须与背包的坐标轴对齐。
问：在背包内物品不重叠的情况下，能获得的最大总价值是多少？
输入描述
第一行四个整数 n, m, p, q （1 ≤ n,m,p ≤ 50, 1 ≤ q ≤ 100）
接下来 q 行，每行四个整数 wi, hi, di, ci（1 ≤ wi,hi,di ≤ max(n, m, p), 1 ≤ ci ≤ 10^6）
输出描述
一个整数，表示最大总价值。

这个算法题有解决方案吗

Answer 1

Assume there are critical rules which must be followed and these rules will be set up in each step of placing object into box one by one. Otherwise, just randomly picking object and throw into box. The probability of getting the max value in such way is almost 0, which means it is practically impossible to use brute force approach without rules.