鋼條切割問題
一家鋼條廠推出了不同長度的鋼條對應不同價格的回收策略，如果小於現在有n米長的鋼條，應該怎麼切割使得銷售後收益Rn最大？
|
長度n |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
價格p |
1 |
5 |
8 |
9 |
10 |
17 |
17 |
20 |
24 |
30 |
動態規劃
|
n=1 |
則不用切割，收益R1 = 1 |
|
n=2 |
可以選擇切割成1 1，收益R = 1+1=2； 也可以不切割 R=5，相比較不切割更優，R2=5。 |
|
n=3 |
切割成1 1 1，R=1+1+1=3 或者不切割 3，R=8 R3 = 8 是最優的 |
|
n=4 |
切割方案有0+4，1+3，2+2 max（0+9，1+8，5+5） 所以R4 =10=R2 +R2最優 |
|
n=5 |
切割方案有0+5，1+4，2+3 max（0+10，1+10，5+8） 所以R5=13= R2 +R3最優 |
|
n=6 |
切割方案有0+6，1+5，2+4，3+3 max（0+17，1+13，5+10，8+8） 所以R6=17= 0 +6最優 |
|
n=7 |
R7=0+7，1+6，2+5，3+4 max（0+17，1+17，5+13，8+10），R7=18 |
================================
1. 有一根 8 公尺長的鋼管，可以切成任意數段的鋼管出售(假設鋼管只能切成 1 公尺的整數倍長)，依據下列的價目表，請問此鋼管最佳切法所得到的最高總售價為何? (2)
|
長度 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
價目 |
2 |
10 |
16 |
18 |
20 |
34 |
34 |
40 |
ANS
（動態規劃 背包問題）
|
n=1 |
則不用切割，收益R1 = 2 |
|
n=2 |
可以選擇切割成1 1，收益R = 2+2=4； 也可以不切割 R=10，相比較不切割更優，R2=10。 |
|
n=3 |
切割成1 1 1，R=2+2+2=6 或者不切割 3，R=16 R3 = 16 是最優的 |
|
n=4 |
切割方案有0+4，1+3，2+2 max（0+18，1+16，10+10） 所以R4 =20=R2 +R2最優 |
|
n=5 |
切割方案有0+5，1+4，2+3 max（0+20，2+20，10+16） 所以R5=22= R1 +R4最優 |
|
n=6 |
切割方案有0+6，1+5，2+4，3+3 max（0+34，2+22，10+20，16+16） 所以R6=34= 0 +6最優 |
|
n=7 |
R7=0+7，1+6，2+5，3+4 max（0+34，2+34，10+22，16+20） 所以R7=36=3 +4最優 |
|
n=8 |
R8=0+8，1+7，2+6，3+5，4+4 max（0+40，2+36，10+34，16+22，22+20） 所以R8=44=2 +6最優 |
1個6公尺1個2公尺=34+10=44
===========================================
16. 「無限背包問題」又被稱為「完全背包問題」，即有n 種物品和一個耐重上限為W 的背包，對於每種物品有其重量大小weight 和所屬價值cost。假設每種物品都有「無限多個」可以索取，在不超過背包耐重上限之下，求出可放入背包的最大物品價值總和。
下列為無限背包問題的程式碼，假設背包耐重上限為9 個單位，四種物品的重量大小與所屬價值如下表，呼叫find(weight, cost, 4, 9)後輸出結果為何？(此題3 分)
find(weight, cost, 4, 9)
|
weight |
2 |
3 |
4 |
5 |
|
cost |
3 |
4 |
5 |
6 |
i=0,j=2～8
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
w[0]=2 c[0]=3
|
dp[2]=max(dp[2],dp[2-2]+3); |
dp[2]=max(0,0+3); |
dp[2]=3 |
|
dp[3]=max(dp[3],dp[3-2]+3); |
dp[3]=max(0,0+3); |
dp[3]=3 |
|
dp[4]=max(dp[4],dp[4-2]+3); |
dp[4]=max(0,3+3); |
dp[4]=6 |
|
dp[5]=max(dp[5],dp[5-2]+3); |
dp[5]=max(0,3+3); |
dp[5]=6 |
|
dp[6]=max(dp[6],dp[6-2]+3); |
dp[6]=max(0,6+3); |
dp[6]=9 |
|
dp[7]=max(dp[7],dp[7-2]+3); |
dp[7]=max(0,6+3); |
dp[7]=9 |
|
dp[8]=max(dp[8],dp[8-2]+3); |
dp[5]=max(0,9+3); |
dp[8]=12 |
i=1,j=3～8
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
w[1]=3 c[1]=4
|
dp[3]=max(dp[3],dp[3-3]+4); |
dp[3]=max(3,0+4); |
dp[3]=4 |
|
dp[4]=max(dp[4],dp[4-3]+4); |
dp[4]=max(6,0+4); |
dp[4]=6 |
|
dp[5]=max(dp[5],dp[5-3]+4); |
dp[5]=max(6,3+4); |
dp[5]=7 |
|
dp[6]=max(dp[6],dp[6-3]+4); |
dp[6]=max(9,4+4); |
dp[6]=9 |
|
dp[7]=max(dp[7],dp[7-3]+4); |
dp[7]=max(9,6+4); |
dp[7]=10 |
|
dp[8]=max(dp[8],dp[8-3]+4); |
dp[5]=max(12,7+4); |
dp[8]=12 |
i=2,j=4～8
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
w[2]=4 c[2]=5
|
dp[4]=max(dp[4],dp[4-4]+5); |
dp[4]=max(6,0+5); |
dp[4]=6 |
|
dp[5]=max(dp[5],dp[5-4]+5); |
dp[5]=max(7,0+5); |
dp[5]=7 |
|
dp[6]=max(dp[6],dp[6-4]+5); |
dp[6]=max(9,3+5); |
dp[6]=9 |
|
dp[7]=max(dp[7],dp[7-4]+5); |
dp[7]=max(10,4+5); |
dp[7]=9 |
|
dp[8]=max(dp[8],dp[8-4]+5); |
dp[8]=max(12,6+5); |
dp[8]=12 |
i=3,j=5～8
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
w[3]=5 c[3]=6
|
dp[5]=max(dp[5],dp[5-5]+6); |
dp[5]=max(6,0+6); |
dp[5]=7 |
|
dp[6]=max(dp[6],dp[6-5]+6); |
dp[6]=max(9,0+6); |
dp[6]=9 |
|
dp[7]=max(dp[7],dp[7-5]+6); |
dp[7]=max(9,3+6); |
dp[7]=9 |
|
dp[8]=max(dp[8],dp[8-5]+6); |
dp[8]=max(12,4+6); |
dp[8]=12 |