小编Pau*_*ina的帖子

我一直想知道是否有可能以递归或"分而治之"的方式解决这个问题.这是我的问题的可视化:

Input:
22 // point no 1
35 // point no 2
5  // ...
44
45
20
46

Output: 2 // point with number 2 has got the lowest sum (87)

我知道如何以迭代的方式做到这一点,但我正在考虑更优化的事情.

当有1个房产时,我确实理解那里发生了什么.当有超过1个属性时,我遇到了解背包问题的问题.

我必须编写一个使用带有2个属性的背包算法的程序.老师告诉我们,它必须在一个3d数组中完成.我无法想象这样的阵列会是什么样子.

让我们说这是我的意见:

4 3 4 // number of records below, 1st property of backpack, 2nd property  of backpack
1 1 1 // 1st property, 2nd property, cost
1 2 2 // 1st property, 2nd property, cost
2 3 3 // 1st property, 2nd property, cost
3 4 5 // 1st property, 2nd property, cost

输出看起来像这样:

4    // the cheapest sum of costs of 2 records
1 3  // numbers of these 2 records

输出的解释:2组记录适合第1行输入:

(1) - 记录编号1和记录编号3

  1 1 …

当有超过1个属性时,我遇到了解背包问题的问题.当有1个房产时,

我必须编写一个使用带有2个属性的背包算法的程序.老师告诉我们,它必须在一个3d数组中完成.错误的实现将导致O(2 ^ n)处理时间.我无法想象这样的阵列会是什么样子.

让我们说这是我的意见:

4 3 4 // number of records below, 1st property of backpack, 2nd property  of backpack
1 1 1 // 1st property, 2nd property, cost
1 2 2 // 1st property, 2nd property, cost
2 3 3 // 1st property, 2nd property, cost
3 4 5 // 1st property, 2nd property, cost

输出看起来像这样:

4    // the cheapest sum of costs of 2 records
1 3  // numbers of these 2 records

输出的解释:2组记录适合第1行输入:

(1) - 记录编号1和记录编号3 …

我想找到两个顶点之间最便宜的路径,我可以选择一条我可以免费使用的路径,例如:

顶点1和6之间最便宜的路径是1-3-4-5-6 - 我免费进入边缘1-3(费用30),它给我总成本21.

除了逐个检查所有路径之外还有其他方法吗？

就像tittle说的那样.整数<0,10 ^ 18>