DP问题之背包问题

1：01背包问题

问题：给出n个物品，每个物品只能使用一次，每个物品有相应的体积与价值，你可以选择总体积不超过m的物品放入背包，求能得到的最大价值

思路：建立一个二维的DP矩阵，dp[i][j]表示把前i个物品装入体积为j的背包能得到的最大价值，从小问题扩展到大问题

朴素版：

int n, m;
int v[1010], w[1010];
int dp[1010][1010];

void solve(){
	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 = 1; j <= m; j ++){
			dp[i][j] = dp[i - 1][j];
			if(j - v[i] >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
            //这里物品的体积不能超过背包的大小
		}
	}
	
	cout << dp[n][m];
}

可以用滚动数组来优化空间复杂度，我们可以观察到，其实每一层都是从上一层的某些信息继承而来的，而且用的是当前 j 对应的前面的信息，所以我们的第二重for循环就不能从前开始枚举，因为从前开始枚举我们就会用当前层的信息来覆盖实际存储在dp[i]里面的上一层的信息，当我们往后计算的时候其实是需要上一层的信息，也就是dp[i-1]的信息，但是它已经被我计算出来的当前层的信息污染了，所以我们需要从后往前处理防止污染

滚动数组优化：

int n, m;
int v[1010], w[1010];
int dp[1010];

void solve(){
	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 >= v[i]; j --){
			dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
		}
	}
	
	cout << dp[m];
}

2：完全背包问题

问题：在01背包的基础上，每个物品有无限个，你可以选取放入背包

思路：同样是建立一个二维的DP矩阵，我们用dp[i][j]表示在前i个物品每个物品选择一定的数量放入背包所取得的最大价值，代码实现就枚举一下每个物品的选取数量

朴素版：

int n, m;
int v[1010], w[1010];
int dp[1010][1010];

void solve(){
	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 = 1; j <= m; j ++){
			dp[i][j] = dp[i - 1][j];
			for(int k = 0; k * v[i] <= j; k ++){
				dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
			}
		}
	}
	
	cout << dp[n][m];
}

优化思路：我们可以发现

dp[i][j] = max(dp[i][j], dp[i - 1][j - 1 * v[i]] + 1 * w[i], dp[i - 1][j - 2 * v[i]] + 2 * w[i] ,
.....,dp[i - 1][j - k * v[i]] + k * w[i]);

dp[i][j - v[i]] = max(dp[i][j - v[i]], dp[i - 1][j - 2 * v[i]] + 1 * w[i], dp[i - 1][j - 3 * v[i]] + 2 * w[i] ,
.....,dp[i - 1][j - (k + 1) * v[i]] + k * w[i]);

所以 dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i])

优化版：

int n, m;
int v[1010], w[1010];
int dp[1010][1010];

void solve(){
	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 = 1; j <= m; j ++){
			dp[i][j] = dp[i - 1][j];
			if(v[i] <= j) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
		}
	}
	
	cout << dp[n][m];
}

同理，我们也可以像01背包一样进行滚动数组优化，这里和01背包的滚动数组优化略有不同，我们的第二重for循环直接从v[i]开始，应为我们的背包大小必须至少大于等于物品的大小才至少可以放一个，这里我们的dp[i][j - v[i]]其实是本层的信息而不是上一层的信息，也就是我们用本层处理出来的信息来更新本层后面的信息，所以我们不用像01背包一样怕本层计算出来的信息污染了上一层的信息

滚动数组优化：

int n, m;
int v[1010], w[1010];
int dp[1010];

void solve(){
	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 ++){
			dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
		}
	}
	
	cout << dp[m];
}

3：多重背包

问题：给出n给物品，每个物品的体积是v， 价值是w， 最多可以选择 L 件， 求通过选择一些物品能得到的最大价值

思路：朴素版和完全背包问题一样，枚举每个物品的选择件数决定放不放入背包即可

朴素版：

int v[110], w[110], l[110];
int dp[110][110];

void solve(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i ++){
		cin >> v[i] >> w[i] >> l[i];
	}	
	
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			dp[i][j] = dp[i - 1][j];
			for(int k = 0; k <= l[i] && k * v[i] <= j; k ++){
				dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
			}
		}
	}
	
	cout << dp[n][m] << '\n';
}

优化思路：这里的多重背包问题可以通过二进制优化的方式达到用01背包的方式来求解，我们可以发现，一个数字是可以用一些小于他的二的幂组合来表示的，实际上就是二进制的转换，比如7 = 2 ^ 2 + 2 ^ 1 + 2 ^ 0, 所以我们可以把一个数量为 L 的数字拆成logn组单独的物品，这些单独组的物品实际上是可以用来表示0 - L的物品选择次数的，然后做一下01背包即可，同理它是可以类似于01背包进行滚动数组优化的

二进制优化+滚动数组优化：

const int N = 25000, mod = 998244353;
const int Mod = 1e9 + 7, INF = 0x3f3f3f3f;

int v[N], w[N];
int dp[N];

void solve(){
	int n, m;
	cin >> n >> m;
	int idx = 0;
	for(int i = 1; i <= n; i ++){
		int v1, w1, l1;
		cin >> v1 >> w1 >> l1;
		int u = 1;
		while(u <= l1){
			idx ++;
			l1 -= u;
			v[idx] = u * v1;
			w[idx] = u * w1;
			u <<= 1;
		}
		if(l1 > 0){
			idx ++;
			v[idx] = l1 * v1;
			w[idx] = l1 * w1;
		}
	}
	n = idx;
	for(int i = 1; i <= n; i ++){
		for(int j = m; j >= v[i]; j --){
			dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
		}
	}
	
	cout << dp[m] << '\n';
}

4：分组背包

问题：有n个物品和一个大小为m的容器，每个物品属于一个组钟，每组物品只能选择一个放入袋子中，求最大收益

思路：这里其实和01背包以及完全背包有点像，这里我们的目标不是单个物品了，而是每个组，我们的dp[i][j]其实是在前i组取体积不超过j的物品的最大的价值，然后我们内部枚举一下选择哪个物品即可

int n, m, v[1010], w[1010], a[1010], dp[1010][1010];
vector<int> c[1010];//存储每一组物品的下标

void solve(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i ++){
		cin >> a[i] >> v[i] >> w[i];
		c[a[i]].push_back(i);
	}
	
	for(int i = 1; i <= 1000; i ++){
		for(int j = 0; j <= m; j ++){
			dp[i][j] = dp[i - 1][j];
			for(auto k : c[i]){
				if(v[k] <= j) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[k]] + w[k]);
			}
		}
	}
	
	cout << dp[1000][m];
}

同理可得滚动数组优化

int n, m, v[1010], w[1010], a[1010], dp[1010];
vector<int> c[1010];

void solve(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i ++){
		cin >> a[i] >> v[i] >> w[i];
		c[a[i]].push_back(i);
	}
	
	for(int i = 1; i <= 1000; i ++){
		for(int j = m; j >= 0; j --){
			for(auto k : c[i]){
				if(v[k] <= j) dp[j] = max(dp[j], dp[j - v[k]] + w[k]);
			}
		}
	}
	
	cout << dp[m];
}

5：二维背包问题

问题：有 n 个物品，你有一个体积为 m 的背包，你的体力为 k ，每个物品的体积是 v ，价值是 w ，需要消耗体力 t ，求在消耗体力不超过 k 的情况下选择不超过 m 的体积的物品的最大价值

思路：做法其实和01背包的做法是一样的，只是在原来的二维数组的基础上加上一维，dp[i][j][L]表示的是在前i个物品钟选择体积不超过j的物品并且消耗 L 点体力的情况下的最大价值，同理可以通过滚动数组优化掉一维

int v[110], w[110], t[110];
int dp[110][110];

void solve(){
	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> t[i];
	for(int i = 1; i <= n; i ++){
		for(int j = m; j >= v[i]; j --){
			for(int l = k; l >= t[i]; l --){
				dp[j][l] = max(dp[j][l], dp[j - v[i]][l - t[i]] + w[i]);
			}
		}
	}
	
	cout << dp[m][k] << '\n';
}