# 演算法課程題解 - 動態規劃\: 背包問題

# 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 的情況， ... 以此類推

<!---
尋求更好的解釋方式
--->

### 程式碼

//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 實作

### 程式碼

//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}
$$

### 程式碼

//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 演算法 題解`