一道IT笔试题( 二 )
通过对列的初等变换得到:
将
解得有:
(
为自由变量)则
可得约束为：
通过整数规划(integer programming, IP)求目标线性函数S的最小值我编不下去了QAQ...去看paper吧:Johnson.2000.JOC.ProgressforIntegerProgramming
■网友
你的想法很好，就是这样的。
■网友
你的想法是对的，优先使用10，缩减到(-10, 10)范围内再用1，3来枚举
■网友
求解最短路径，或者说广度优先搜索#include \u0026lt;iostream\u0026gt;#include \u0026lt;map\u0026gt;#include \u0026lt;deque\u0026gt;static void Search(int iInit, int iTarget, int vAdds, int N){\tstd::map\u0026lt;int, int\u0026gt; mapPrevs;\tmapPrevs.insert(std::map\u0026lt;int, int\u0026gt;::value_type(iTarget, iTarget));\tstd::deque\u0026lt;int\u0026gt; qNodes;\tqNodes.push_back(iTarget);\twhile (!qNodes.empty())\t{\t\tint iCurrent = qNodes.front();\t\tqNodes.pop_front();\t\tif (iCurrent == iInit)\t\t\tbreak;\t\tfor (int k = 0; k \u0026lt; N; ++k)\t\t{\t\t\tint iNext = iCurrent + vAdds;\t\t\tif (mapPrevs.find(iNext) == mapPrevs.end())\t\t\t{\t\t\t\tqNodes.push_back(iNext);\t\t\t\tmapPrevs = iCurrent;\t\t\t}\t\t}\t}\tfor (int i = iInit; ; )\t{\t\tstd::cout \u0026lt;\u0026lt; i \u0026lt;\u0026lt; " ";\t\tint iPrev = mapPrevs;\t\tif (i == iPrev)\t\t\tbreak;\t\ti = iPrev;\t}\tstd::cout \u0026lt;\u0026lt; std::endl;}int main(){\tint vAdds = {-1, 1, -3, 3, -10, 10};\tint N = sizeof (vAdds) / sizeof (int);\tSearch(18, 2, vAdds, N);\tSearch(11, 18, vAdds, N);\tSearch(-1, -1, vAdds, N);\tSearch(-10, 25, vAdds, N);\treturn 0;}
■网友
我是这么想的:先把得到 0～9 最简单的按钮次数记录到数组接下来方便了，arr+y%10如果有误见笑了。
■网友
1-9是背包问题：f(x) = min(f(x - k) + 1)，f(x - k) = min(f(x) + 1, f(x - k))超过10时f(x) = min(f(x - 10) + 1, f(x - 9) + 3),而fabs(f(x) - f(x-1))\u0026lt;=1，所以这里应该是贪心。int f(x){ if(x == 0) return 0; if(x\u0026lt;= 9) return 背包; return x / 10 + f(x % 10);}
■网友
典型的动态规划嘛。
■网友
此为乱答：既然是按键，按太多肯定不爽。把1-10000温差的最短按键穷举出来。温差为key，按法为value 存到redis。之后需要多少温差，直接取即可，瞬发
推荐阅读
- 王者荣耀李白能不能出肉
- 大三学生准备日本留学过程中要不要准备考研
- 工作3、4的人怎样转行当警察
- 游戏中有哪些让人感动的情节
- 华威大学计算机本科咋样
- 为啥没人做好KTV的UI
- 为啥现在没有一家信用评级系统的公司
- 上海或苏州有没有比较好的大数据培训机构
- 纸质书籍还有生存的余地没
- 30岁的人生，想自学一门编程并从事，这个选择怎样呢