# 演算法課程題解 - 動態規劃\: 背包問題 # UVa 674 ## 題目 http://domen111.github.io/UVa-Easy-Viewer/?674 在美國有幾種硬幣,分別為 `cent`, `penny`, `nickle`, `dime`, `quarter`, `half-dollar` - penny = 1 cent - nickel = 5 cents - dime = 10 cents - quarter = 25 cents - half-dollar = 50 cents 現在給你一個正整數 $n$,表示 cent,請問使用以上的硬幣共有多少的表示方式 ## 想法 By Koios 如果 $m$ cent 可以被表示出來,那麼 $m+1, m+5, m+10, m+25, m+50$ 也一定可以被表示出來 不過為了避免重複計算,要有順序的計算組合數量 也就是說,把每種表示方式都依照幣值由小到大排列,以 $11$ 來說可以看成 - `1 1 1 1 1 1 1 1 1 1 1` - `1 1 1 1 1 1 5` - `1 5 5` - `1 10` 我們先計算出只有使用 $1$ cent 的情況,再來看 $5$ cent 的情況, ... 以此類推 <!--- 尋求更好的解釋方式 ---> ### 程式碼 ```cpp= //By Koios1143 #include<iostream> using namespace std; int n, dp[7500], cent[5] = {1, 5, 10, 25, 50}; int main(){ dp[0] = 1; for(int i=0 ; i<5 ; i++){ for(int j=0 ; j<7490 ; j++){ if(j - cent[i] < 0) continue; dp[j] += dp[j-cent[i]]; } } while(cin>>n){ cout<<dp[n]<<"\n"; } return 0; } ``` # UVa 10664 ## 題目 http://domen111.github.io/UVa-Easy-Viewer/?10664 有一群人要出門度假,他們認為兩輛汽車可以容納所有人的行李 然而因為負重越大,耗油量也會增加,沒人希望自己的車比較耗油 因此,他們希望能將行李平均分散在兩台車上 現在告訴你每個行李的重量分別是多少,假設每台車無論多重的行李都可以容納,請問是否可以將行李平分成重量完全相同的兩堆 ## 想法 By Koios 既然要平均分配,那麼總重量必定不是奇數 並且,如果總重量為 $m$,如果 $m/2$ 是可以被組合出來的,那一定有解(因為剩下來的就是另一堆) 對於每個行李都可以選擇要不要選 定義 $dp[i][j]$ 表示前 $i$ 個行李組出總重量為 $j$ 的方法數 則有轉移式 $$ dp[i][j] = dp[i-1][j] + dp[i-1][j-weight[i]] $$ 也就是說方法數包含了要選 $i$ 以及不選 $i$ 兩種情況 並且 $$ dp[i][j] = 1 \quad \texttt{if weight[i] == j} $$ 這裡以 Top-down 實作 ### 程式碼 ```cpp= //By Koios1143 #include<iostream> #include<sstream> using namespace std; int t, arr[25], dp[25][205]; string s; int sol(int m, int tot){ if(tot <= 0 || m < 0) return 0; if(dp[m][tot]) return dp[m][tot]; dp[m][tot] = sol(m-1, tot) + sol(m-1, tot-arr[m]); return dp[m][tot]; } int main(){ cin>>t; getchar(); while(t--){ int tot = 0, n = 0, m; for(int i=0 ; i<25 ; i++){ for(int j=0 ; j<205 ; j++){ dp[i][j] = 0; } } getline(cin, s); stringstream ss; ss<<s; while(ss>>m){ arr[n] = m; tot += m; dp[n][m]++; n++; } if(tot % 2 != 0){ cout<<"NO\n"; } else{ tot /= 2; if(sol(n-1, tot)){ cout<<"YES\n"; } else{ cout<<"NO\n"; } } } return 0; } ``` # UVa 10130 ## 題目 http://domen111.github.io/UVa-Easy-Viewer/?10130 在一個商店當中有 $N$ 種商品,每種商品的數量都可以看做是無限多 現在商店正在超級特惠活動,每個東西都超便宜,以致於有很多人來搶購 每個人都有一個負重上限,也就是說最多能拿總重量為 $w_i$ 的物品,並且每種商品一個人最多只能拿一個 現在有 $G$ 個人來商店搶購,告訴你每個商品的重量以及價值,也告訴你每個人的最大負重分別為多少 請問這 $G$ 個人最多總共能搬走總價值多少的商品 ## 想法 By Koios 每種商品對於每個人來說都只有選或是不選兩種 定義 $dp[i][j]$ 表示前 $i$ 種商品在負重還有 $j$ 的時候最多可以拿走總價值多少的商品 定義 $price[i]$ 表示第 $i$ 種商品的價值 定義 $weight[i]$ 表示第 $i$ 種商品的重量 則有轉移式 $$ \begin{cases} dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+price[i]) \quad j-weight[i] >= 0 \\ dp[i][j] = dp[i-1][j] \quad j-weight[i] < 0 \end{cases} $$ ### 程式碼 ```cpp= //By Koios1143 #include<iostream> using namespace std; int t, n, g, price[1005], weight[1005], dp[1005][1005]; int sol(int m, int tot){ if(tot <= 0 || m < 0) return 0; if(dp[m][tot]) return dp[m][tot]; // 不選第 m 種商品的最大總價值 dp[m][tot] = sol(m-1, tot); // 選第 m 種商品的最大總價值 if(tot - weight[m] >= 0){ dp[m][tot] = max(dp[m][tot], sol(m-1, tot-weight[m]) + price[m]); } return dp[m][tot]; } int main(){ cin>>t; while(t--){ for(int i=0 ; i<1005 ; i++){ for(int j=0 ; j<1005 ; j++){ dp[i][j] = 0; } } cin>>n; for(int i=0 ; i<n ; i++){ cin>>price[i]>>weight[i]; } cin>>g; int ans = 0; for(int i=0, w ; i<g ; i++){ cin>>w; ans += sol(n-1, w); } cout<<ans<<"\n"; } return 0; } ``` ###### tags: `SCIST 演算法 題解`