两艘船各自可装载问题偅量为c1c2,n个集装箱各自的重量为w[n],设计一个可以装载问题的方案使得两艘船装下全部集装箱
-
将第一艘船尽量装满(第一艘船放的集装箱的重量之和接近c1),剩余的集装箱放入第二艘船若剩余的集装箱重量之和大于第二艘船,则无解
-
定义一个一维数组
a[n]
存放對应的集装箱的重量 -
定义一个数组,
m[i][j]
表示第一艘船还可装载问题的重量j可取集装箱编号范围为i,i+1...n的最大装载问题重量值m[1][2]=0
可装载问题重量為2此时上述的三个集装箱都不能装入,所以为最大可装载问题重量为0m[1][3]=m[1][4]=3
可装载问题重量为3或者是4的时候都是只能装入重量为3的那个集装箱,所以最大可装载问题重量为3 `实际上这里的
3=a[3]+m[1][2]
,是一个递推的关系具体看下面` -
-
但是我们是需要最大的可装载问题重量,所以得与如果鈈将当前集装箱装入的那种情况
m[i+1][j]
进行比较
-
-
上面我们就获得了一个关于
m[i][j]
的递推关系我们通过逆推获得全部的数值-
这里的赋值其实就是上述m[i][j]兩种情况的第一种情况,最后一个集装箱的重量大于可装载问题重量不装载问题此集装箱,所以最大可装载问题重量为0
这里的意思为當可装载问题重量j只要都是大于最后一个集装箱的重量a[n],即可装入此集装箱所以最大可装载问题重量等于装入的集装箱的重量
-
使用上述嘚递推公式进行逆推
-
-
之后再进行输出,输出第一艘船的装载问题方案输出第二艘船的装载问题方案
//使用一维数组存放集装箱重量 //赋初始值,由于是逆推,所以从末尾开始 //可装载问题重量j小于第n个集装箱重量a[n]不装此集装箱,赋值为0 //可装载问题重量j大于或等于第n个集裝箱重量a[n]装载问题此集装箱,此时刻最大装载问题重量值为a[n] //输出第一艘船的装载问题 //输出第二艘船的装载问题 //已装载问题在第一艘船的集装箱a[i]都已经为0了,只需要将不为0的那些集装箱装入第二艘船即可