杭州城乡建设厅网站,wordpress 删除自豪,蚌埠网站制作公司哪家好,广告加工厂目录 1 基础知识2 模板3 工程化 1 基础知识
暂无。。。
2 模板
暂无。。。
3 工程化
题目1#xff1a;潜水员。
解题思路#xff1a;DP。
状态定义f[i][j][k]#xff1a;从前i个物品中选#xff0c;氧气至少为j#xff0c;氮气至少为k的最小方案数。
状态转移潜水员。
解题思路DP。
状态定义f[i][j][k]从前i个物品中选氧气至少为j氮气至少为k的最小方案数。
状态转移以下情况的最小值
不选择第i个物品即f[i-1][j][k]。选择第i个物品即f[i - 1][j - v1[i]][k - v2[i]] w[i]。状态从i-1层转移过来的故从大到小循环。
同样地可以将状态优化到二维。
初始化f[i][j] 0x3f3f3f3ff[0][0] 0。
最终答案返回f[n][m]。
C代码如下
#include iostream
#include cstringusing namespace std;const int N 30, M 90;
int n, m, k;
//n表示氧气需要的量
//m表示氮气需要的量
//k表示气缸的个数
int f[N][M];int main() {memset(f, 0x3f, sizeof f);f[0][0] 0;cin n m k;while (k--) {int a, b, c;cin a b c;for (int i n; i 0; --i) {for (int j m; j 0; --j) {f[i][j] min(f[i][j], f[max(i - a, 0)][max(j - b, 0)] c);}}}cout f[n][m] endl;return 0;
}题目2背包问题求解具体方案数。
解题思路求具体方案数不难关键是求解字典序最小的有些困难。
C代码如下
#include iostreamusing namespace std;const int N 1010;
int n, m;
int v[N], w[N];
int f[N][N];int main() {cin n m;for (int i 1; i n; i) cin v[i] w[i];for (int i n; i 1; --i) {for (int j 0; j m; j) {f[i][j] f[i 1][j];if (j v[i]) f[i][j] max(f[i][j], f[i 1][j - v[i]] w[i]);}}int j m;for (int i 1; i n; i) {if (j v[i] f[i][j] f[i 1][j - v[i]] w[i]) {cout i ;j - v[i];}}return 0;
}题目3机器分配。
解题思路分组背包问题求解最大价值和具体方案。
C代码如下
#include iostreamusing namespace std;const int N 20;
int n, m;
int w[N][N]; //第i组第k台的价值
int f[N][N];
int s[N]; //第i组选了第多少台int main() {cin n m;for (int i 1; i n; i) {for (int k 1; k m; k) {cin w[i][k];}}for (int i 1; i n; i) {for (int j 0; j m; j) {f[i][j] f[i-1][j];for (int k 1; k m; k) {if (j k) {f[i][j] max(f[i][j], f[i-1][j - k] w[i][k]);}}}}cout f[n][m] endl;int j m;for (int i n; i 1; --i) {for (int k 1; k m; k) {if (j k f[i][j] f[i-1][j - k] w[i][k]) {s[i] k;j - k;break;}}}for (int i 1; i n; i) {cout i s[i] endl;}return 0;
}题目4金明的预算方案。
解题思路分组背包问题。
C代码如下
#include iostream
#include vector
#include unordered_mapusing namespace std;const int M 32010;
int n, m;
int f[M];int main() {cin m n;//读入n个物品struct ITEM {ITEM(int a, int b) : v(a), w(b) {} //构造函数int v;//体积int w;//价格};vectorITEM items;items.emplace_back(ITEM(-1,-1));unordered_mapint, vectorint son; //son[i]表示物品i的附件们for (int i 1; i n; i) {int v, p, q;cin v p q;ITEM item(v, p * v);items.emplace_back(item);if (q 0) {//第i件物品是主件son[i].emplace_back(-1);son[i].pop_back();} else {//第i件物品是附件它的主件是qson[q].emplace_back(i);}}//分组背包问题求解for (auto [i, vec] : son) {//遍历每一个主件i和它的附件vecfor (int j m; j 0; --j) {//考虑每一个附件for (int k 0; k 1 vec.size(); k) {int v items[i].v, w items[i].w;//遍历每个附件for (int ii 0; ii vec.size(); ii) {if (k ii 1) {//选择了第ii个附件v items[vec[ii]].v;w items[vec[ii]].w;}}if (j v) f[j] max(f[j], f[j - v] w);}}}cout f[m] endl;return 0;
}题目5开心的金明。
解题思路01背包问题即可。
C代码如下
#include iostreamusing namespace std;const int M 30010;
int n, m;
int f[M];int main() {cin m n;for (int i 1; i n; i) {int v, p;cin v p;int w v * p;for (int j m; j v; --j) {f[j] max(f[j], f[j - v] w);}}cout f[m] endl;return 0;
}
