JXFCZX — 砝码称重1(DFS+背包)
发布日期:2021-07-01 00:18:43
浏览次数:3
分类:技术文章
本文共 1200 字,大约阅读时间需要 4 分钟。
题目链接:
时间:1 秒 空间:512 MB题目描述
现有n个砝码,重量分别为a1,a2,a3,……,an,在去掉m个砝码后,问最多能称量出多少不同的重量(不包括0)。
输入描述
输入的第1行为有两个整数n和m,用空格分隔
第2行有n个正整数a1,a2,a3,……,an,表示每个砝码的重量。
输出描述
输出仅包括1个整数,为最多能称量出的重量。
样例输入
3 1
1 2 2
样例输出
3
数据范围及提示
样例说明
在去掉一个重量为2的砝码后,能称量出1,2,3共3种重量。
数据规模
对于20%的数据,m=0;
对于50%的数据,m≤1; 对于50%的数据,n≤10; 对于100%的数据,n≤20,m≤4,m<n,ai≤100。
解题思路
先DFS出哪些是留下的n-m个砝码,然后再跑01背包,找出最多的那一个。
Accepted Code:#includeusing namespace std;int n, m, max_ = 0;int s[25], v[25], vis[25], dp[2005];void edge() { int ans = 0; memset(dp, 0, sizeof(dp)); dp[0] = 1; for (int i = 0; i < n - m; i++) { for (int j = 2000; j >= v[i]; j--) { if (!dp[j] && dp[j - v[i]]) { ans++; dp[j] = 1; } } } if (ans > max_) max_ = ans;}void DFS(int k, int t) { if (k >= n - m) { if (k == n - m) edge(); return ; } for (int i = t; i < n; i++) { if (!vis[i]) { vis[i] = 1; v[k] = s[i]; DFS(k + 1, i); vis[i] = 0; } }}int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) scanf("%d", s + i); DFS(0, 0); printf("%d\n", max_); return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/91038314 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月14日 10时48分16秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
linux 下 mysql下保存进去数据为乱码的解决办法(centos5.x)
2019-05-01
内存对齐详解
2019-05-01
秋招总结(一)-C++归纳
2019-05-01
秋招总结(三)-操作系统归纳
2019-05-01
基于UDP的服务器端/客户端
2019-05-01
优雅地断开套接字连接--套接字半关闭
2019-05-01
域名及网络地址
2019-05-01
套接字的多种可选项
2019-05-01
多进程服务器端 ---(1) 进程
2019-05-01
多进程服务器端 ---(2) *
2019-05-01
进程间通信
2019-05-01
线程 互斥量 信号量——多线程服务器端的实现
2019-05-01
制作HTTP服务器端
2019-05-01
带缓冲I/O 和不带缓冲I/O的区别与联系
2019-05-01
带缓冲I/O与不带缓冲I/O:文件I/O和标准I/O库
2019-05-01
浅谈标准I/O缓冲区
2019-05-01
exec函数详解
2019-05-01
传输层:TCP UDP
2019-05-01
套接字编程简介
2019-05-01
基本TCP套接字编程
2019-05-01