关注
把阿里内推时做的那题做了一便,该写的坑还是得填。。 // 自己的写的,不一定对,但是能过给的样例。 // 主要思路就是 深度搜索,终止条件就是 不能再加组合时,和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; }
查看原帖
点赞 评论
相关推荐

点赞 评论 收藏
分享

点赞 评论 收藏
分享
04-21 16:05
北京邮电大学 Java 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 职场捅娄子大赛 #
272656次浏览 2433人参与
# 如何KTV领导 #
50730次浏览 390人参与
# 华泰证券Fintech星战营 #
11012次浏览 143人参与
# 华为求职进展汇总 #
4604766次浏览 28075人参与
# 如果不工作真的会快乐吗 #
111647次浏览 924人参与
# 一人一个landing小技巧 #
47920次浏览 818人参与
# 互联网行业现在还值得去吗 #
13058次浏览 48人参与
# 节后第一天上班,我的精神状态 #
5603次浏览 69人参与
# 2025,我想...... #
42738次浏览 429人参与
# 00后45度躺现状 #
88811次浏览 454人参与
# 租房前辈的忠告 #
161623次浏览 6195人参与
# 应届生应该先就业还是先择业 #
102580次浏览 622人参与
# 产品实习,你更倾向大公司or小公司 #
147714次浏览 1921人参与
# 校招入职后的感受 #
264810次浏览 2629人参与
# 职场上哪些行为很加分? #
188083次浏览 2312人参与
# 产品人专业大盘点 #
42576次浏览 292人参与
# 秋招最大的收获是什么? #
28964次浏览 286人参与
# 简历无回复,你会继续海投还是优化再投? #
63491次浏览 682人参与
# 运营人求职交流聚集地 #
130214次浏览 972人参与
# 扒一扒那些奇葩实习经历 #
54555次浏览 846人参与
# 嵌入式岗知多少 #
35378次浏览 419人参与