动态规划

动态规划：

1. 状态表示
   集合：集合(如只考虑前 $i$ 个物品的选法)

   属性：集合的某种属性，最大值，最小值，数量等

2. 状态计算

   集合的划分过程：第 $i$ 个物品选 0 个、选 1 个……

背包问题

0-1 背包：

$f(i,j)=\max (f(i-1,j),f(i-1,j-v_i)+w[i])$

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++){
            f[i][j] = f[i-1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
}

// 一维版本(空间复杂度优化)
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i ++)
        for(int j = m; j >= i; j --)
            f[j] = max(f[j], f[j-v[i]] + w[i]);
        
    cout << f[m] << endl;
}

完全背包问题：

$f[i,j]=\max (f[i-1,j-kv_i]+kw[i])$

// 朴素做法
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
            for(int k = 0; k * v[i] <= j; k ++)
            	f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);
    cout << f[n][m] << endl;
}

优化：

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
由上两式，可得出如下递推关系： 
                        f[i][j]=max(f[i-1][j], f[i,j-v]+w)

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++){
            f[i][j] = f[i-1][j];
            if(j >= v[i])f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
}

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i ++)
        for(int j = v[i]; j <= m; j ++){
            if(j >= v[i])[j] = max([j], f[j-v[i]] + w[i]);
        }
    cout << f[m] << endl;
}

f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包

f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题

多重背包：

$f[i,j]=\max (f[i-1,j-kv_i]+kw[i])$

// 朴素做法, 与完全背包朴素做法类似
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> s[i];
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
            for(int k = 0; k * v[i] <= j && k <= s[i]; k ++)
            	f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);
    cout << f[n][m] << endl;
}

// 二进制优化, 转化为 0-1 背包
#include <iostream>
using namespace std;
const int N = 23000, M = 2020;// 2000 * log 2000
int n, m;
int v[N], w[N];
int f[N];
int main(){
    cin >> n >> m;
    int cnt = 0;
    for(int i = 1; i <= n; i ++){
        int a, b, s; cin >> a >> b >> s;
        int k = 1;
        while(k <= s){
            cnt ++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k <<= 1;
        }
        if(s > 0){
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt;
    for(int i = 1; i <= n; i ++)
        for(int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j-v[i]] + w[i]);
    cout << f[m];
}

分组背包：

max(第 i 组物品不选，选第 i 组物品的第 k 个)

$$f[i,j]=max(f[i-1,j],f[i-1,j-v]+w)$$

#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i ++){
		cin >> s[i];
		for(int j = 0; j < s[i]; j ++)
			cin >> v[i][j] >> w[i][j];
	}
	for(int i = 1; i <= n; i ++)
		for(int j = m; j >= 0; j --)
			for(int k = 0; k < s[i]; k ++)
				if(v[i][k] <= j)
					f[j] = max(f[j], f[j-v[i][k]] + w[i][k]);
	cout << f[m] << endl;
}

Q.E.D.