郑州做网站建设哪家好,桂林百姓生活网,做网站安全联盟解,网站开发与设计需要哪些技术目录 1 基础知识2 模板3 工程化 1 基础知识
暂无。。。
2 模板
暂无。。。
3 工程化
题目1#xff1a;货币系统。
解题思路#xff1a;完全背包模型求方案数。
状态定义f[i][j]#xff1a;从前i个物品中选体积恰好为j的方案数。 状态转移f[i][j]#xff0c;以下情况… 目录 1 基础知识2 模板3 工程化 1 基础知识
暂无。。。
2 模板
暂无。。。
3 工程化
题目1货币系统。
解题思路完全背包模型求方案数。
状态定义f[i][j]从前i个物品中选体积恰好为j的方案数。 状态转移f[i][j]以下情况的累加和
不选择第i个物品即f[i-1][j]。选择第i个物品1次即f[i-1][j-v[i]]。选择第i个物品2次即f[i-1][j-2*v[i]]。……选择第i个物品max次即f[i-1][j-max*v[i]]。
状态转移可以简化成
状态转移f[i][j]以下情况的累加和
不选择第i个物品即f[i-1][j]。选择第i个物品1次~max次的累加和为f[i][j-v[i]]。
初始化f[0][0] 1。
最终答案为f[n][m]。
同样的也可以将状态降维C代码如下
#include iostreamusing namespace std;const int M 3010;
int n, m;
long long f[M];int main() {cin n m;f[0] 1;for (int i 0; i n; i) {int x;cin x;for (int j x; j m; j) {f[j] f[j-x];}}cout f[m] endl;return 0;
}题目2货币系统求最简的面值表示。
解题思路完全背包求方案数的应用。
C代码如下
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 110, M 25010;
int n, m;
int v[N];
int f[M];int main() {int T;cin T;while (T--) {cin n;for (int i 0; i n; i) cin v[i];sort(v, v n);int res 0;m v[n - 1];memset(f, 0, sizeof f);f[0] 1;for (int i 0; i n; i) {if (f[v[i]] 0) res 1;for (int j v[i]; j m; j) {f[j] f[j - v[i]];}}cout res endl;}return 0;
}题目3混合背包问题。
解题思路完全背包归为一类体积从小到大枚举01背包和多重背包归为一类体积从大到小枚举。
C代码如下
#include iostreamusing namespace std;const int M 1010;
int n, m;
int f[M];int main() {cin n m;for (int i 0; i n; i) {int v, w, s;cin v w s;if (s 0) {//完全背包问题for (int j v; j m; j) {f[j] max(f[j], f[j - v] w);}} else {if (s -1) s 1;for (int k 1; k s; k 1) {for (int j m; j k * v; --j) {f[j] max(f[j], f[j - k * v] k * w);}s - k;}if (s) {for (int j m; j s * v; --j) {f[j] max(f[j], f[j - s * v] s * w);}}}}cout f[m] endl;return 0;
}
