求树的“最小分支”——仓库问题的解法

我有一个仓库存放货物。每件物品占用一定数量的仓库空间,成本为美元。

现在,因为仓库已经满了,我期待着新的交货,我必须腾出一些空间-不少于新的交货将占用,但我也必须尽量减少我的损失。换言之,我必须通过扔掉一些物品来清空至少X立方米的仓库空间,确保这些物品的价值是可能的最小值。

例子: 如果X=10m3,那么我宁愿扔掉占用20m3,价值1000美元的物品,而不是占用10m3,但价值2000美元的物品。 当然,在实际计算中,有必要扔掉不止一个项目,可能是5个、10个甚至20个。

我想的是将上述问题表示为一棵树,其中节点表示清空空间的体积,边表示 lost value 损失价值 沿着从树根到节点的边缘。

我不确定这是否是一个好方法,因为例如,仓库满树中的100个项目在第一个深度级别上有100个节点,在第二个级别上有100*99=9900个节点等等,所以这很快就开始是可行的。

对于这类问题,有没有更好的方法,或者甚至是一些经过验证的算法(我不知道)?