蟻本のＤＰ

ナップサック問題
重さと価値がそれぞれWi,Viであるようなｎ個の品物があります。これらの品物から、重さの総和がＺを超えないように選んだ時の価値の総和の最大値を求めなさい。

お馴染み？のＤＰ

```
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int Z;
int w[110], v[110];
int dp[110][10010];
int main() {
	cin >> n >> Z;
	for (int i = 0; i < n; ++i)
		cin >> w[i] >> v[i];
	
	for (int w = 0; w <= Z;++w)dp[0][w] = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= Z; ++j) {
			if (j >= w[i])dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j]);
			else dp[i + 1][j] = dp[i][j];
		}
	}
	cout << dp[n][Z];
}
```
素人だし何回もやるべきでしょまあうんアホだし。
最長共通部分列問題
２つの文字列S1S2,,,,Snとt1t2,,,,,tmが与えられます。これら２つの共通部分文字列の長さの最大値を求めなさい。ただし、文字列S1S2,,,,,Snの部分文字列とは、S(i1)S(i2),,,,S(im)と表すことのできる文字列のことを言います。
1<=n,m<=1000
dp[i][j]:=S1S2,,,,,,Siとt1t2,,,,tjに対するＬＣＳの長さとする。
するとS1S2,,,,,Si+1とt1,,,,tj+1に対する共通部分列は
Si+1=tj+1ならば共通部分列の後ろにSi+1を繋げたもの。
S1,,,Siとt1,,,tj+1に対する共通部分列
S1,,,Si+1とt1,,,,tjに対する共通部分列
のどれかであるので、漸化式がたてられる。

```
#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
char s[1010], t[1010];
int dp[1010][1010];
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; ++i)cin >> s[i];
	for (int j = 0; j < m; ++j)cin >> t[j];
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (s[i + 1] == t[j + 1]) {
				dp[i + 1][j + 1] = dp[i][j] + 1;
			}
			else {
				dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
			}
		}
	}
	cout << dp[n][m];
}
```
charとstringの違いがまだいまいちつかめていないな。

個数制限なしナップサック
重さと価値がそれぞれwi,viであるようなｎ種類の品物があります。これらの品物から、重さの総和がWを超えないように選んだ時の、価値の総和の最大値を求めなさい。ただし、同じ種類の品物をいくつでも選ぶことができます。

ナップサックの同じ品物が選べるバージョン
漸化式を変える必要がある。なんかいろいろ蟻本には書いてあるけど初心者だし漸化式も直感的にまあそうじゃねってなったしコードだけでいいか

```
#include<iostream>
#include<algorithm>
using namespace std;
int n, W;
int w[110], v[110];
int dp[110][10010];
int main() {
	cin >> n >> W;
	for (int i = 0; i < n; ++i)cin >> w[i] >> v[i];
	for (int i = 0; i < n; ++i)dp[0][i] = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < W; ++j) {
			if (j >= w[i])
				dp[i + 1][j] = max(dp[i + 1][j - w[i]] + v[i], dp[i][j]);
			else
				dp[i + 1][j] = dp[i][j];
		}
	}
	cout << dp[n][W];
	return 0;
}
```
ナップサック問題その２
重さと価値がそれぞれwi,viであるようなn個の品物があります。これらの品物から、重さの総和がWを超えないように選んだ時の価値の総和の最大値を求めなさい。ただし、
・1<=n<=100
・1<=wi<=10000000
・1<=vi<=100
・1<=W<=1000000000
重さが大きく、価値が小さいので、漸化式を改良して計算しやすくする。
dp[i+1][j]:=i番目までの品物から価値の総和がjとなるように選んだ時の、重さの総和の最小値と定義する。初期値は、
dp[0][0]=0
dp[0][j]=INFとなる。（解が存在しない場合は十分大きな値INF）
dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
という漸化式が成り立ち、最終的な答えはdp[n][j]<=Wとなる最大のjである。

```
#include<iostream>
#include<algorithm>
using namespace std;
int n, W;
int w[110], v[110];
int dp[110][10010];
const int INF = 100000000000000;
int main() {
	cin >> n >> W;
	for (int i = 0; i < n; ++i)cin >> w[i] >> v[i];
	dp[0][0] = 0;
	for (int i = 0; i < 10010; ++i)dp[0][i] = INF;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= 10010; ++j) {
			if (j < v[i]) {
				dp[i + 1][j] = dp[i][j];
			}
			else {
				dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
			}
		}
	}
	int res = 0;
	for (int i = 0; i <= 10010; i++)
		if (dp[n][i] <= W)res = i;
	cout << res;
	return 0;
}
```
個数制限付き部分和問題
n種類の数aiがそれぞれmi個ずつあります。これらの中からいくつか選び、その総和をちょうどKとすることができるか判定しなさい。
・1<=n<=100
・1<=ai,mi<=100000
・1<=K<=100000
これももう一度やります。
もし、dp[i+1][j]:=i番目まででjが作れるかのように定義すると、漸化式は、
dp[i+1][j]=(0<=k<=miかつ、k*ai<=jでdp[i][j-k*ai]が真となるkが存在する)

```
#include<iostream>
#include<algorithm>
using namespace std;
int n, k;
int a[110], m[110];
bool dp[110][100010];
int main() {
	cin >> n >> k;
	for (int i = 0; i < n; ++i)cin >> a[i] >> m[i];
	dp[0][0] = true;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= k; j++) {
			for (int l = 0; l <= m[i] && k*a[i] <= j; ++l) {
				dp[i + 1][j] |= dp[i][j - l * a[i]];
			}
		}
	}
	if (dp[n][k])cout << "yes";
	return 0;
}
```
となるが、これは計算量が多すぎる。
dp[i+1][j]:=i番目まででjを作る際に余る最大のi番目の個数(作れない場合は-1)
と定義すると、i-1番目まででjを作れるなら、i番目をmi個残してjを作ることができます。また、i番目まででj-aiを作る際にi番目をk個残すことができるならば、i番目をk-1個残してjを作ることができます。従って漸化式は、
dp[i][j]>=0の時dp[i+1][j]=miとなる
```

分割数
n個の互いに区別できない品物を、m個以下に分割する方法の総数を求め、Mで割った余りを答えなさい
・1<=m<=n<=1000
・2<=M<=10000
数学ガールにわかりやすい解説が載っていた。
p(n,m):=整数nを順序を区別せずにm以下の自然数の和に分ける場合の数。と定義すると、
p(n,m) = p(n-m,m)+p(n,m-1)が成り立つ。初期条件などは、
p(0,m) = 1
p(n,1) = 1
p(n,m) = p(n,n)(n<m)

```
#include<iostream>
using namespace std;
int n, m, M;
int dp[1010][1010];
int main() {
	cin >> n >> m >> M;
	for (int i = 0; i <= m; ++i)
		dp[i][0] = 1;
	for (int j = 0; j <= n; ++j)
		dp[1][j] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= m; ++j) {
			if (j - i >= 0) {
				dp[i][j] = (dp[i][j - i] + dp[i - 1][j])%M;
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[m][n];
	return 0;
}
```
コードはたぶんあってるはずなのになぜか答えがあわないなんで？まあいいや放置

重複組み合わせ
n種類の品物があり、i番目の品物はai個あります。異なる種類の品物同士は区別できますが、同じ種類の品物同士は区別できません。これらの品物の中からm個選ぶ組み合わせの総数を求め、Mで割った余りを答えなさい
dp[i+1][j]:=i番目までの品物からj個選ぶ組み合わせの総数
むずい