NO.88十六届蓝桥杯备战|动态规划-多重背包|摆花(C++)

多重背包

多重背包问题有两种解法：

1. 按照背包问题的常规分析⽅式，仿照完全背包，第三维枚举使⽤的个数；
2. 利⽤⼆进制可以表⽰⼀定范围内整数的性质，转化成01 背包问题。
   ⼩建议：并不是所有的多重背包问题都能⽤⼆进制优化，⽽且优化版本的代码很⻓。因此，如果时间复杂度允许的情况下，能不优化就不优化
   解法⼀：常规分析
3. 状态表⽰：
   dp[i][j]表⽰：从前i 个物品中挑选，总重量不超过j 的情况下，最⼤的价值。
   dp[n][m]就是最终结果。
4. 状态转移⽅程：
   根据第i 个物品选的个数，可以分x[i] + 1种情况：
   a. 选0 个：价值为dp[i - 1][j] ；
   b. 选1 个：价值为dp[i - 1][j - w[i]] + v[i] ；
   c. 选2 个：价值为dp[i - 1][j - 2 × w[i]] + 2 × v[i] ；
   d. …
   e. 选x[i]个：价值为dp[i - 1][j - x[i] × w[i]] + x[i] × v[i] 。
   因为要的是最⼤价值，所以dp[i][j]等于上述所有情况的最⼤值。但是要注意j-k*w[i]要⼤于等于0，并且不能按照完全背包的⽅式优化。
5. 初始化：
   全部为0 就不影响最终结果
6. 填表顺序：
   从上往下每⼀⾏，每⼀⾏从左往右

#include <bits/stdc++.h>
using namespace std;const int N = 110;int n, m;
int x[N], w[N], v[N];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> x[i] >> w[i] >> v[i];for (int i = 1; i <= n; i++)for (int j = m; j >= 0; j--)for (int k = 0; k <= x[i] && k * w[i] <= j; k++){f[i][j] = max(f[i][j], f[i-1][j - k*w[i]] + k * v[i]);}cout << f[n][m] << endl;return 0;
}

空间优化：

#include <bits/stdc++.h>
using namespace std;const int N = 110;int n, m;
int x[N], w[N], v[N];
int f[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> x[i] >> w[i] >> v[i];for (int i = 1; i <= n; i++)for (int j = m; j >= 0; j--)for (int k = 0; k <= x[i] && k * w[i] <= j; k++){f[j] = max(f[j], f[j - k*w[i]] + k * v[i]);}cout << f[m] << endl;return 0;
}

解法⼆：转化成01背包问题
优化⽅式：⽤⼆进制将x[i]个物品分组。
连续的⼆进制数有⼀个性质，就是$2^0\sim 2^k$能够表⽰区间[1, 2^(k+1) - 1]⾥⾯所有的整数。⽐如：

• 1, 2, 4, 8可以表⽰[1, 15]内所有的整数。具体原因可以参考整数的⼆进制表⽰，正好1, 2, 4, 8对应⼆进制表⽰中每⼀位的权值，所以排列组合起来就可以表⽰[1,15]内所有的整数。
• 同理1, 2, 4 就可以表⽰[1, 7]内所有的整数。
  根据这样⼀个性质，我们就可以把x[i]拆成⼀些⼆进制数再加上多出来的数，这样的⼀组数就可以表⽰[1,x[i]]内所有的整数，问题就变成了01背包
  ⽐如x[i] = 9，w[i] = 2, v[i] = 3 ：
• 9 = 1 + 2 + 4 + 2 ；
• 分成4 组，每组的重量和价值分别为(2, 3)、(4, 6)、(8, 12)、(4, 6)

#include <bits/stdc++.h>
using namespace std;const int N = 110 * 5;int n, m;
int w[N], v[N], pos;
int f[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++){int x, y, z; cin >> x >> y >> z;//2进制拆分int t = 1;while (x >= t){pos++;w[pos] = t * y;v[pos] = t * z;x -= t;t *= 2;}if (x) //处理剩余{pos++;w[pos] = x * y;v[pos] = x * z;}}//01背包for (int i = 1; i <= pos; i++)for (int j = m; j >= w[i]; j--)f[j] = max(f[j], f[j - w[i]] + v[i]);cout << f[m] << endl;return 0;
}

P1077 [NOIP 2012 普及组] 摆花 - 洛谷

题意：每⼀种花可以选[0, a[i]]个，在总数恰好等于m 时的总⽅案数
正好是多重背包求⽅案数的模型，我们可以⽤多重背包的思考⽅式来解决这道题。

1. 状态表⽰：
   dp[i][j]表⽰：从前i个花中挑选，正好摆放j 个花盆时的⽅案数。
2. 状态转移⽅程：
   根据第i 种花选的个数k(0 ≤ k ≤ min(j, a[i])) 分情况讨论：

• 如果当前花选了k 盆，之前的花要去凑够j - k 盆，总的⽅案数就是dp[i - 1][j - k] ；
• 因为要的是总⽅案数，所以最终结果应该是k 的变化过程中的状态的总和。
  dp[i][j] = dp[i][j] + dp[i - 1][j - k]

3. 初始化：
   dp[0][0] = 1 ，相当于起始状态，为了让后续的填表有意义，不然全都是0 。
4. 填表顺序：
   从上往下每⼀⾏，每⼀⾏从左往右。
   这道题就不能⽤⼆进制优化，因为这道题的背包，限定条件和价值是⼀⼀对应的，并且求的是⽅案数。如果⽤⼆进制优化会统计多余的情况，⽐如：

• 有两个物品，个数分别是3, 2 ，要凑成总和为4 。
• 拆分之后为(1, 2)、(1, 1) ，跑⼀遍01 背包之后，结果是 3 ，但是实际情况应该是2 。
• 原因是1,2,1被统计了2次。但是在实际情况⾥，第⼀个物品全选，第⼆个物品选1个，只属于1种情况，⽽01背包的逻辑会统计两次

#include <bits/stdc++.h>
using namespace std;const int N = 110, MOD = 1e6 + 7;int n, m;
int a[N];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];f[0][0] = 1;for (int i = 1; i <= n; i++){for (int j = m; j >= 0; j--){for (int k = 0; k <= j && k <= a[i]; k++){f[i][j] = (f[i][j] + f[i-1][j-k]) % MOD;        }}}cout << f[n][m] << endl;return 0;
}

空间优化

#include <bits/stdc++.h>
using namespace std;const int N = 110, MOD = 1e6 + 7;int n, m;
int a[N];
int f[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];f[0] = 1;for (int i = 1; i <= n; i++){for (int j = m; j >= 0; j--){for (int k = 1; k <= j && k <= a[i]; k++){f[j] = (f[j] + f[j-k]) % MOD;        }}}cout << f[m] << endl;return 0;
}

单独考虑k==0

#include <bits/stdc++.h>
using namespace std;const int N = 110, MOD = 1e6 + 7;int n, m;
int a[N];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];f[0][0] = 1;for (int i = 1; i <= n; i++){for (int j = m; j >= 0; j--){f[i][j] = f[i-1][j];for (int k = 1; k <= j && k <= a[i]; k++){f[i][j] = (f[i][j] + f[i-1][j-k]) % MOD;        }}}cout << f[n][m] << endl;return 0;
}