解题思路:直接dfs,但是这里用到了一个剪枝,降低了时间复杂度
注意事项:
参考代码:
#include<bits/stdc++.h> using namespace std; int n,m; int x[30]; int flag; int dfs(int num,int i) { int a; if(num==0)//当重量被减为0时说明可以 { return 1; } else if(i==n) { return 0; } flag=dfs(num,i+1)||dfs(num-x[i],i+1)||dfs(num+x[i],i+1);//剪枝如果前面的正确了后面的就不用做了 } int main() { int Max=0; cin>>n>>m; for(int i=0;i<n;i++) { cin>>x[i]; Max+=x[i]; } int w[m+5]; for(int i=0;i<m;i++) { cin>>w[i]; if(Max<w[i])//如果全部砝码加起来都没有物品重的话就说明不可以 { cout<<"NO"<<endl; continue; } dfs(w[i],0); if(flag) { cout<<"YES"<<endl; flag=0; } else { cout<<"NO"<<endl; } } return 0; }
0.0分
0 人评分
简单的a+b (C语言代码)浏览:495 |
C语言训练-最大数问题 (C语言代码)浏览:633 |
【密码】 (C语言代码)浏览:333 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:668 |
求组合数 (C语言代码)浏览:1159 |
WU-输入输出格式练习 (C++代码)浏览:1082 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:542 |
哥德巴赫曾猜测 (C语言代码)浏览:2352 |
求圆的面积 (C语言代码)浏览:1670 |
The 3n + 1 problem (C语言代码)浏览:554 |