上面是一个当砝码为8,4,2,1 四个砝码时的搜索情况 ,物品我们假设是放在天平的左边的,我们可以把砝码放在天平的左边 也可以放在天平的右边 ,分别代表着 +w[i] 和 -w[i] 直到我们要称的重量为0了 便称出了该物体 的重量。本题一个关键点就是你要遍历所有的放置情况 这样就涵盖了 所有砝码的放置情况 。比如 放置了8 后面就考虑4,2,1的放置情况 放置完4后 就考虑放置2,1的情况 而不用考虑放置8的情况 因为前面在放置8时 后面包括了放置4的情况
由于我对深度搜索了解的也不多 欢迎大家批评指正 一起学习!!(图画的有点丑。。)
参考代码:
#include<iostream> #include<algorithm> #include<string.h> #include<cmath> using namespace std; int n,m,flag; int w[25],k[25]={0}; bool cmp(const int &x, const int &y) { return x > y; } void dfs(int s,int x) //好了 关键来了 { if (flag){ //退出条件 return ; } if (s == 0) //s等于0表示称出了结果 { flag = 1; return ; } if (abs(s)>k[x]){//如果物品的重量大于剩下的砝码能表示的最大重量 return ; } for (; x<n; x++) //每个x表示搜索的起点 { //两种情况 dfs(s-w[x],x+1); //把砝码放在天平的右边 dfs(s+w[x],x+1); //把砝码放在天平的左边 } } int main() { int s; cin>>n>>m; //输入砝码和物品的个数 for (int i=0; i<n ;i++) { cin>>w[i]; //输入砝码的重量 } sort(w,w+n,cmp); //将砝码从大到小排序 //集合砝码和 for (int i=n-1; i>=0; i--) { k[i] = w[i]+k[i+1]; //依次求出前(n-i)个砝码能称出的最大重量 } while (m--) { cin>>s; //输入待称物品的重量 flag = 0; //flag=0表示未称出 dfs(s,0); if (flag){ //flag=1表示称出了物品重量 cout<<"YES"<<endl; } else{ cout<<"NO"<<endl; } } return 0; }
0.0分
3 人评分
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:450 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:748 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:676 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:449 |
WU-图形输出 (C++代码)浏览:800 |
C语言程序设计教程(第三版)课后习题6.6 (C语言代码)浏览:349 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:534 |
IP判断 (C语言描述,蓝桥杯)浏览:1092 |
1908题解浏览:633 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:398 |