“求价值最大和”,毋庸置疑,用动态规划。此类题目属于动态规划中的一个特殊类别——“背包问题”。
PS:背包问题可以分为三种——
- 0/1背包问题——物品只有选/不选两种状态,求最大价值和
- 子集背包问题——分割等和子集问题
- 完全背包问题——物品可以无限选,求可以组合成目标值的选法
设当前个数为i,当前最大背包容量为j,那么dp[i][j]
表示“背包容量为j时,在前i个物品中选择的最大价值和”。有如下状态公式(设w为重量数组,v为价值数组):
- 如果j-w[i-1]>=0,
dp[i][j] = max(dp[i-1][j-w[i-1]]+v[i-1], dp[i-1][j])
- 如果j-w[i-1]<0,
dp[i][j] = dp[i-1][j]
- 基准1:
dp[0][..]=0
- 基准2:
dp[..][0]=0
解释状态公式:
- 如果当前背包重量减去当前物品重量后还有余地,那么当前最大价值和为“选当前物品”和“不选当前物品”两种情况的较大值
- 如果当前背包重量减去当前物品重量后没有剩余空间了,那么当前最大价值和为“不选当前物品”的最大价值和
- 基准1: 在物品数量为0的情况下,最大价值和永远为0
- 基准2: 在背包容量为0的情况下,最大价值和也永远为0
代码如下:
// // Created by jt on 2020/8/26. // #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int N, M; cin >> N >> M; vector<int> w, v; for (int i = 0; i < N; ++i) { int a; cin >> a; w.push_back(a); } for (int i = 0; i < N; ++i) { int a; cin >> a; v.push_back(a); } vector<vector<int>> dp(N+1, vector<int>(M+1, 0)); for (int i = 1; i <= N; ++i) { for (int j = 1; j <= M; ++j) { dp[i][j] = j-w[i-1] >= 0 ? max(dp[i-1][j-w[i-1]]+v[i-1], dp[i-1][j]) : dp[i-1][j]; } } cout << dp[N][M] << endl; }