我最近遇到过这个问题.假设x轴上有n个点,x [0],x [1] .. x [n-1].让与这些点中的每一个相关联的权重为w [0],w [1] ... w [n-1].从0到n-1之间的任何点开始,目标是覆盖所有点,使得w [i]*d [i]的总和最小化,其中d [i]是到达第i个点所覆盖的距离.起点.
示例:
假设点数为:1 5 10 20 40
假设权重为:1 2 10 50 13
如果我选择从点10开始并选择移动到点20然后到5然后再到40然后最终到1,那么加权和将变为10*0 + 50*(10)+ 2*(10 + 15)+ 13*(10 + 15 + 35)+ 1*(10 + 15 + 35 + 39).
我试图通过贪婪的方法解决它,从具有最大相关权重的点开始并移动到第二个最大权重点,依此类推.但算法不起作用.有人可以指点一下解决这个问题必须采取的方法吗？