Coins
2022/5/28 23:24:19
本文主要是介绍Coins,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Coins
多重背包可行性
SCUACM2022集训前训练-动态规划 - Virtual Judge (vjudge.net)
本题若用二进制拆解多重背包会T,可用单调队列优化
但由于本题是求可行性而非最优化,可用进行剪枝来减小复杂度
\(f[i]\) :\(i\) 能否被表示出来
\(used[i]\) :当前这种货币,表示到 \(i\) 块钱,已经用了多少张
可第一层循环枚举货币种类,第二层枚举要表示的面值
这三种情况就不用判断了(\(j\) 块钱已经能被表示了;\(j-a[i]\) 都没法被表示,加一个 \(a[i]\) 也不行;表示$j-a[i] $ 已经花光了这种货币)
f[j] || !f[j-a[i]] || used[j-a[i]] >= c[i]
复杂度 \(O(n*m)\)
#include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <cmath> using namespace std; typedef long long ll; const int N = 1e2 + 10, M = 1e5 + 10; int a[N], c[N]; int used[M]; bool f[M]; int n, m; int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); while(cin >> n >> m, n || m) { for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> c[i]; memset(f, false, sizeof f); f[0] = true; for (int i = 1; i <= n; i++) { memset(used, 0, sizeof used); for (int j = 1; j <= m; j++) { if (f[j] || !f[j-a[i]] || used[j-a[i]] >= c[i]) continue; f[j] = true; used[j] = used[j-a[i]] + 1; } } int ans = 0; for (int i = 1; i <= m; i++) ans += f[i]; cout << ans << endl; } return 0; }
这篇关于Coins的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain