洛谷P1441 砝码称重(搜索,dfs+dp)
2024-10-16 00:27:16
\(n\) 的范围为 \(n \le 20\) ,\(m\) 的范围为 \(m \le 4\) 。
暴力遍历每一种砝码去除情况,共有 \(n^m\) 种情况。
对于剩余砝码求解可以组合的重量种类数。简单dp求解。复杂度为 \(O(n\times n\times m)\) 。
时间复杂度为 \(O(n^m \times n\times n \times m)\) 。实际复杂度应该比这个小很多,剪枝效果明显。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 25;
const int maxm = 2005;
int n, m, ans, sum;
int vis[maxn], a[maxn], f[maxm];
void solve()
{
for(int i = 0; i <= sum; i++) f[i] = 0;
f[0] = 1;
int tot = 0, ret = 0;
for(int i = 1; i <= n; i++){
if(vis[i] == 1) continue;
for(int j = tot; j >= 0; j--){
if(f[j] == 1 && f[j + a[i]] == 0){
ret++; f[j + a[i]] = 1;
}
}
tot += a[i];
}
ans = max(ans, ret);
}
void dfs(int now, int step)
{
if(step == m + 1){
solve();
return;
}
for(int i = now; i <= n; i++){
vis[i] = 1;
dfs(i + 1, step + 1);
vis[i] = 0;
}
}
int main()
{
scanf("%d%d", &n, &m);
sum = 0;
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
sum += a[i];
}
ans = 0;
dfs(1, 1);
printf("%d\n", ans);
return 0;
}
最新文章
- NLP&;数据挖掘基础知识
- WordPress酷炫CSS3读者墙代码
- 【代码笔记】iOS-向服务器传JSON数据的两种方式
- throttle在程序中的作用
- 微博MySQL优化之路--dockone微信群分享
- FileDataSource java的文件操作
- 图片上传前的预览(PHP)
- javascript之冒泡算法
- ios开发——实战OC篇&;SQLite3的实际应用
- 转:ASCII码表_全_完整版
- Spring-mvc junit单元测试中 如何回滚?
- document.write()相关
- http协议报头信息和主体鉴别
- 【转】搜索引擎选择: Elasticsearch与Solr
- ConfirmCancelDialog【确认取消对话框】
- [TCP/IP] 传输层-ethereal 抓包分析TCP包
- Vmware虚拟中克隆主机没IP地址?怎么解决?
- svn安装和使用
- Git中的bash与CMD的区别
- Js时间格式[转载]
热门文章
- 如何搭建Vue环境?
- HDFS网络拓扑概念及机架感知(副本节点选择)
- sublime text3插件安装及使用
- Sql Server主副本和辅助副本间账号同步以及权限同步
- 用命令行远程导出MySQL数据
- 简单易用的leetcode开发测试工具(npm)
- TP5.1+Vue前后端分离实践
- Python内建函数enumerate()用法及在for循环应用
- 攻防世界--simple-check-100
- jQ:";对象不支持“first”属性或方法";IE内核下不兼容first()、chilrdren()方法的处理