关注
把阿里内推时做的那题做了一便,该写的坑还是得填。。 // 自己的写的,不一定对,但是能过给的样例。 // 主要思路就是 深度搜索,终止条件就是 不能再加组合时,和best对比。 #include <iostream> #include <string> #include <sstream> using namespace std; int bom[9][10]; int product[10]; int cnt[10]; int res_count[10]; int res_sum = 0; int zero_count = 0; int n,m; char c ; void isbest(){ int tmp_count = 0; int sum = 0; for(int i =0; i <m;i++){ if(product[i] == 0){ tmp_count ++; } sum += product[i]; } if(tmp_count>zero_count ||(tmp_count == zero_count&&sum< res_sum)){ zero_count = tmp_count; for(int i =0; i < m;i++){ res_count[i] = cnt[i]; } res_sum = sum; } } // m 为组合数量 void dfs(int m){ for(int i =0; i < m;i++){ if(product[i] <0) return; } isbest(); for(int i = 0; i < m;i++){ cnt[i]++; // 使用组合i for(int j = 0;j < m;j++){ product[j] -= bom[i][j]; } dfs(m); // 回滚组合i for(int j = 0;j < m;j++){ product[j] += bom[i][j]; } cnt[i]--; } } int main(){ // m 为组合数, n为商品数目 cin >>n>>c>>m; // 读取商品数量 for(int i = 0 ; i < n;i++){ if(i <n-1){ cin >> product[i]; cin >> c; }else if(i == n-1) { cin >> product[i]; } } cin.ignore(); //读取组合 string s; stringstream str; for(int i = 0; i < m;i++){ getline(cin,s,'\n'); int pos = s.find(","); int start = 0; int n_copy = 0; while(n_copy<n+1){ if(n_copy >0&n_copy < n){ str << s.substr(start,pos-start) <<endl; str>>bom[i][n_copy-1]; str.str(""); }else if(n_copy == n){ str << s.substr(start,s.size()-start)<<endl; str>>bom[i][n_copy-1]; str.str(""); } start = pos+1; pos = s.find(",",start); n_copy++; } } dfs(m); for(int i =0; i<m;i++) { if(res_count[i] != 0) cout << "bom" <<i+1 <<"*"<< res_count[i]<<endl; } return 0; }
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
- 1... 挑战 26 届最速转正失败——我做错了什么4.0W
- 2... 我的校园恋爱正式结束了1.2W
- 3... 从后端的角度聊一聊:2728届想要搞开发的同学现在最应该干什么?9045
- 4... 25的兄弟们还在战斗吗?7388
- 5... 毕业照和春招结束代表着我的学生时代落幕了7170
- 6... 坐我后面的妹妹被拉走了!!6860
- 7... 27学院鼠好不容易找到实习,代课被同学举报5701
- 8... 26届游戏客户端暑期实习求职历程5180
- 9... 好想加班好想加班,啊啊我的钱(っ╥╯﹏╰╥c)5014
- 10... 秋招提前上岸,这个机会真的不错!建议大家冲!4853
正在热议
更多
# 职场捅娄子大赛 #
295617次浏览 2910人参与
# 晒一下我的毕业照 #
21942次浏览 182人参与
# 华泰证券Fintech星战营 #
164071次浏览 185人参与
# 华为求职进展汇总 #
4622198次浏览 28162人参与
# 好好告别我的学生时代 #
12633次浏览 258人参与
# 一人一个landing小技巧 #
52936次浏览 862人参与
# 互联网行业现在还值得去吗 #
16235次浏览 54人参与
# 2025,我想...... #
47501次浏览 450人参与
# 如何缓解求职过程中的焦虑? #
2665次浏览 32人参与
# 运营来爆料 #
42584次浏览 320人参与
# 00后45度躺现状 #
92336次浏览 470人参与
# 简历无回复,你会继续海投还是优化再投? #
67139次浏览 692人参与
# 机械人,签完三方你在忙什么? #
48055次浏览 211人参与
# 租房前辈的忠告 #
166972次浏览 6336人参与
# 节后第一天上班,我的精神状态 #
8596次浏览 74人参与
# 嵌入式岗知多少 #
38632次浏览 425人参与
# 如何KTV领导 #
54691次浏览 411人参与
# 记录实习开销 #
10125次浏览 75人参与
# 应届生应该先就业还是先择业 #
105458次浏览 623人参与
# 来聊聊机械薪资天花板是哪家 #
121482次浏览 735人参与
# 你的秋招第一面感觉怎么样 #
69394次浏览 554人参与