假设我们有一个输入:
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;
我确实知道如何解决背包问题,但是我不知道如何解决这个问题。
您可以使用与背包问题相同的方法,但您将拥有一个 3D 表,而不是 2D 矩阵,每个参数都有一个维度(2 个约束 + 索引)。
递归公式将类似,但当然会对两个参数都进行递归公式。
f(item,cost1,cost2) = max {
f(item-1,cost1,cost2),
f(item,cost1-firstCost[i],cost2-secondCost[i]) + profit[i]
}
(基本子句也类似,但有一个额外的维度。)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)