解题思路:
可以用DFS实现。天平两边都可以放砝码。所以砝码有三种状态。
定义一个函数:bool opt(int n,int total,int w)
其中:n表示剩余砝码个数,total表示能称重量,w表示物品重量
1.把第n个砝码放在物品另一侧,则有:opt(n-1,total+fama[n-1],w)
2.把第n个砝码放在与物品同侧,择有:opt(n-1,total-fama[n-1],w)
3.不放第n个砝码,则有:opt(n-1,total,w)
参考代码:
#include <bits/stdc++.h> using namespace std; const int N=25; const int M=11; int fama[N]; //砝码重量 bool opt(int n,int total,int w) //n表示剩余砝码个数,total表示能称重量,w表示物品重量 { if(n<0) return false; if(total==w) //如果总重量等于物体重量 return true; bool A=opt(n-1,total+fama[n-1],w); //把第n个砝码放在物品另一侧 bool B=opt(n-1,total-fama[n-1],w); //把第n个砝码放在与物品同侧 bool C=opt(n-1,total,w); //不放第n个砝码 return A||B||C; } int main() { int n,m; int weight[M]; //物品重量 bool yesno[M]; //是否能称出来 cin>>n>>m; for(int i=0;i<n;i++) cin>>fama[i]; for(int i=0;i<m;i++) { cin>>weight[i]; yesno[i]=opt(n,0,weight[i]); //把该物品是否能称出来的标志放到数组中保存,最后才一起输出 } for(int i=0;i<m;i++) //输出第i个物品能否称出来的标志 { if(yesno[i]) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
0.0分
3 人评分