什么是解决两个属性背包概率的最快方法(What's the fastest way to s

比方说，我们已经有了一个输入：

10 // saying 1st property should be 10(in total)
10 // saying 2d property should be 10 (in total)
5 // saying theres 5 records below
// (1st property) (2nd property) (cost)
2 5 8 
7 3 10 
4 2 9
4 3 5
8 5 15

在这种情况下，输出会像她那样：

22 // lowest possible cost
1 3 4 // indexes of records, we've been using (indexing starts with 1)

 2  5  8
 4  2  9
 4  3  5
+---------
 10 10 22

如果是不可能的方式来实现这些特性是10和10，程序将输出-1; 我不知道如何解决背包问题，但是我有不知道如何解决这个概率。

Answer 1:

您可以使用背包问题的相同的方法，但不是二维矩阵，你将有一个3D表，每个参数（2约束+指数）的尺寸。

该递推公式将是类似的，但当然会为这两个参数来完成。

f(item,cost1,cost2) = max {
               f(item-1,cost1,cost2), 
               f(item,cost1-firstCost[i],cost2-secondCost[i]) + profit[i]
                          }

（基本条款将是类似的为好，但有一个额外的维度。）

文章来源: What's the fastest way to solve knapsack prob with two properties