2023年8月1日发(作者：)
背包问题模板组合背包（普通背包问题，完全背包，多重背包）背包问题⼤部分都是模板题，这⾥整理了组合背包的模板。组合背包：物品的可取数⽬为1，有限个或⽆限个。也就是说该模板适⽤于01背包，完全背包，多重背包———————————————————————对于可取数⽬不为⼀的处理思路：我们将该物品的数⽬，分解成⼏个2的幂次的和1，2，4……， 多余出来的也放进去，再将这些数乘以原价值，原重量，单作不同的物品加进去。为什么要这么做呢？假设我们当我们取k件该物品时，k同样可以看成分解出来的数的组合。然后就是普通背包的思路了。#include
价值
数⽬int dp[40000];inline void inc(int a, int b) { m[cnt] = a, v[cnt++] = b;}//插⼊void trans(int a, int b, int c, int max) {//转换
⼆进制
int tmp = 1; if (c == 233) {//数⽬为233时当作完全背包处理 while (tmp * a <= max) { inc(tmp * a, tmp * b); tmp <<= 1; } } else {//多重背包 while ((tmp << 1) - 1 <= c) { inc(tmp * a, tmp * b); c -= tmp; tmp <<= 1; } if (c != 0)inc(a * c, b * c); }}void find(int max) {//dp int i, j; for (i = 0; i < cnt; i++) { for (j = max; j >= m[i]; j--) { dp[j] = dp[j - m[i]] + v[i] > dp[j] ? dp[j - m[i]] + v[i] : dp[j];//状态转移⽅程 } }}void clear(int can) {//清空（为下次输⼊做准备） cnt = 0; memset(dp, 0, sizeof(int) * (can + 1));}int main() { int n, can, i, a, b, c; while (~scanf("%d%d", &n, &can)) {//数⽬，最⼤质量 for (i = 0; i < n; i++) { scanf("%d%d%d", &a, &b, &c); if (c != 1)trans(a, b, c, can); else inc(a,b); } find(can); printf("%dn", dp[can]); clear(can); }}
2023年8月1日发(作者：)
背包问题模板组合背包（普通背包问题，完全背包，多重背包）背包问题⼤部分都是模板题，这⾥整理了组合背包的模板。组合背包：物品的可取数⽬为1，有限个或⽆限个。也就是说该模板适⽤于01背包，完全背包，多重背包———————————————————————对于可取数⽬不为⼀的处理思路：我们将该物品的数⽬，分解成⼏个2的幂次的和1，2，4……， 多余出来的也放进去，再将这些数乘以原价值，原重量，单作不同的物品加进去。为什么要这么做呢？假设我们当我们取k件该物品时，k同样可以看成分解出来的数的组合。然后就是普通背包的思路了。#include
价值
数⽬int dp[40000];inline void inc(int a, int b) { m[cnt] = a, v[cnt++] = b;}//插⼊void trans(int a, int b, int c, int max) {//转换
⼆进制
int tmp = 1; if (c == 233) {//数⽬为233时当作完全背包处理 while (tmp * a <= max) { inc(tmp * a, tmp * b); tmp <<= 1; } } else {//多重背包 while ((tmp << 1) - 1 <= c) { inc(tmp * a, tmp * b); c -= tmp; tmp <<= 1; } if (c != 0)inc(a * c, b * c); }}void find(int max) {//dp int i, j; for (i = 0; i < cnt; i++) { for (j = max; j >= m[i]; j--) { dp[j] = dp[j - m[i]] + v[i] > dp[j] ? dp[j - m[i]] + v[i] : dp[j];//状态转移⽅程 } }}void clear(int can) {//清空（为下次输⼊做准备） cnt = 0; memset(dp, 0, sizeof(int) * (can + 1));}int main() { int n, can, i, a, b, c; while (~scanf("%d%d", &n, &can)) {//数⽬，最⼤质量 for (i = 0; i < n; i++) { scanf("%d%d%d", &a, &b, &c); if (c != 1)trans(a, b, c, can); else inc(a,b); } find(can); printf("%dn", dp[can]); clear(can); }}
发布评论