免费做网站百度能录入,ios6软件下载网站,东莞哪家纯设计公司做得好,如何进行网络推广二进制分解多重背包
269#xff1a;【例9.13】庆功会 【题目描述】 为了庆贺班级在校运动会上取得全校第一名成绩#xff0c;班主任决定开一场庆功会#xff0c;为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品#xff0c;可以补充他们的精力和体力。 #inc…二进制分解多重背包
269【例9.13】庆功会 【题目描述】 为了庆贺班级在校运动会上取得全校第一名成绩班主任决定开一场庆功会为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品可以补充他们的精力和体力。 #includeiostream
using namespace std;
const int N 5e310, M 6e310;
int m, n, w[N], v[N],s[N], dp[M];
//状态 dp[j] 前i件物品在背包容量不超过j的情况下的最大价值
//状态转移方程 if (j w[i]) dp[j] max(dp[j], dp[j - w[i]] v[i]);
int main() {cin n m; int ww, vv, ss;int id 0;for (int i 1; i n; i) {cin ww vv ss;//输入每种物品的容量、价值、数量//针对ss进行二进制分解for (int j 1; j ss; j 1) {w[id] j * ww;v[id] j * vv;ss - j;}//如果二进制分解后的ss有剩余则按剩余ss倍的物品存储if (ss) {w[id] ss * ww;v[id] ss * vv;ss 0;}}//二进制优化多重背包时间复杂度Onm 其中n是二进制分解后的物品种类//注意二进制分解后的物品种类不再是n是idfor (int i 1; i id; i) {for (int j m; j w[i]; j--) {dp[j] max(dp[j], dp[j - w[i]] v[i]);}}cout dp[m] endl;return 0;
}
二维费用背包
1271【例9.15】潜水员 【题目描述】 潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸一个为氧气一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少 例如潜水员有5个气缸。每行三个数字为氧氮的升量和气缸的重量 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119 如果潜水员需要5升的氧和60升的氮则总重最小为24912或者45号气缸。 你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。 #includeiostream
using namespace std;
/*
二维费用背包(基础就是01背包)
状态dp[j][k] 前i种物品在背包1容量不超过j的情况且背包2容量不超过k的情况下构成的最小价值
状态转移方程 dp[j][k]min(dp[j][k],dp[j-w1[i]][k-w2[i]]v[i]);
*/
const int N 1e3 10, M 1e2 10;
int n, m1, m2;
int w1[N], w2[N], v[N], dp[M][M];
int main() {cin m1 m2 n;for (int i 1; i n; i)cin w1[i] w2[i] v[i];//注意本题求最小价值dp一定初始化为最大memset(dp, 0x3f, sizeof dp);dp[0][0] 0;for (int i 1; i n; i) for (int j m1; j 0; j--) for (int k m2; k 0; k--) dp[j][k] min(dp[j][k], dp[max(0,j - w1[i])][max(0,k - w2[i])] v[i]);cout dp[m1][m2] endl;return 0;
}分组背包 特点n种物品每种物品只有一件分到不同的组中每组最多选一件 状态和状态转移方程同01背包一样 1272【例9.16】分组背包 【题目描述】 一个旅行者有一个最多能装V公斤的背包现在有n件物品它们的重量分别是W1W2...,Wn12...,它们的价值分别为C1,C2,...,Cn1,2,...,。这些物品被划分为若干组每组中的物品互相冲突最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量且价值总和最大。 #includeiostream
#includevector
using namespace std;
/*
分组背包
特点n种物品每种物品只有一件分到不同的组中每组最多选一件
状态和状态转移方程同01背包一样
*/
const int N 40, M 210;
int m, n,t,p, w[N], v[N], dp[M];
int main() {cin m n t;vectorint group[N];for (int i 1; i n; i) {cin w[i] v[i] p;group[p].push_back(i);//根据组号p完成分组}//01背包可以看成特殊的分组背包即每种物品都是单独的一组for (int i 1; i t; i) {for (int j m; j 1; j--) {//针对当前第i组的背包容量j去枚举每件物品选/不选找到其中的最优解dp[j]保证组内最多选一件for (int k 0; k group[i].size(); k) {int id group[i][k];if (j w[id]) dp[j] max(dp[j], dp[j - w[id]] v[id]);}}}cout dp[m] endl;return 0;
}
