比方说,我们有一个输入:
Let's say we've got an input:
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
在此情况下,输出将看起来像这样:
In this case, the output would look like that:
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; 我不知道如何解决背包问题,但我有不知道如何解决这个概率。
If there wasn't possible way to achieve those properties to be 10 and 10, program would output -1; I do know how to solve knapsack problem, however I've got no clue how to solve this prob.
您可以使用的背包问题同样的方法,但不是二维矩阵,你将有一个三维表,每个参数(2约束+指数维度)。
You can use the same approach of knapsack problem, but instead of 2D matrix, you will have a 3D table, a dimension for each parameter (2 constraint + index).
的递推公式将是类似的,但当然这两个参数将被完成。
The recursive formula will be similar, but of course will be done for both parameters.
f(item,cost1,cost2) = max {
f(item-1,cost1,cost2),
f(item,cost1-firstCost[i],cost2-secondCost[i]) + profit[i]
}
(基本条款是相似的,但是有一个额外的维度。)
(Base clauses will be similar as well, but with an extra dimension.)