首页 > 代码库 > nyoj--Divideing Jewels
nyoj--Divideing Jewels
题意:
有十种珠宝用数字表示,现在给你每个珠宝的数量,问可不可以平均分给两个人。
解题思路:
DFS搜索可以写。将完全背包问题转换为搜索问题。
具体代码:
#include<iostream> #include<cstring> #include<stdio.h> using namespace std; int num[15],sum; bool dfs(int n,int m) { if(n==0||m==0) { if(m==0) return true; } else { for(int i=num[n];i>=0;i--) { if(m>=n*i&&dfs(n-1,m-n*i)) { return true; } } } return false; } int main() { int temp=1; while(1) { sum=0; for(int i=1;i<=10;i++) { cin>>num[i]; sum+=i*num[i]; } if(sum==0) break; if(sum%2!=0) printf("#%d:Can‘t be divided.\n",temp); else { if(dfs(10,sum/2)) printf("#%d:Can be divided.\n",temp); else printf("#%d:Can‘t be divided.\n",temp); } temp++; } system("pause"); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。