算法吧 关注：30,583贴子：59,340
- 25回复贴，共1页
楼主终于做出来了，下面分享一下算法。
还是从简单的testcase来想，假如 给的数是 2 3 5 7 10，然后目标数是70，那应该怎么做
维护一个递增的set，存放着当前最接近target的数，以及“可能可以用来构造更加接近target”的数
然后从给的数组来思考，
第一个数是2，是最接近target数，同时也是“可能可以用来构造更加接近target的数”，因为后面的数都比2大，那么2*2是会更加接近target，并且比target小，所以把2加进去这个set。当前set为{2}
第二个数是3，使用upper_bound得到set中比target/3还要大的数，那么把这个数*3加进去set，因为找到了一个更加接近target的数。同时对之前维护set遍历得到i，只要3*i*i不比target大，就把3*i加进那个set，因为这个3*i可能可以用来构造更加接近target,当前set为{2,3,6}
第三个数5之后，set为{2,3,5,6,10,30}
第四个数7之后，set为{2,3,4,6,7,10,70}
第五个数10之后，set为{2,3,6,7,10,70}
那么set中最后一个数就是答案了。其实还是dp的思路，只是转移方程不太好表示出来。
还是从简单的testcase来想，假如 给的数是 2 3 5 7 10，然后目标数是70，那应该怎么做
维护一个递增的set，存放着当前最接近target的数，以及“可能可以用来构造更加接近target”的数
然后从给的数组来思考，
第一个数是2，是最接近target数，同时也是“可能可以用来构造更加接近target的数”，因为后面的数都比2大，那么2*2是会更加接近target，并且比target小，所以把2加进去这个set。当前set为{2}
第二个数是3，使用upper_bound得到set中比target/3还要大的数，那么把这个数*3加进去set，因为找到了一个更加接近target的数。同时对之前维护set遍历得到i，只要3*i*i不比target大，就把3*i加进那个set，因为这个3*i可能可以用来构造更加接近target,当前set为{2,3,6}
第三个数5之后，set为{2,3,5,6,10,30}
第四个数7之后，set为{2,3,4,6,7,10,70}
第五个数10之后，set为{2,3,6,7,10,70}
那么set中最后一个数就是答案了。其实还是dp的思路，只是转移方程不太好表示出来。
