文章
11
粉丝
152
获赞
9
访问
36.0k
思路
使用动态规划的思想,用 weight[1...n] 表示各个物件的重量,多个物件被选择后,最后加上物件 weight[m] 刚好满足总重量为 s ,那么必须满足 s - weight[m] 与前面选择的物件重量之和相等,重复这样操作的时候,s变成了 s - weight[m],物件数量在原有的基础上减少1个,某个被选择的物件是重量weight[n]。从而我们可以利用递归判断是否满足条件:
if(packet(s - weight[n - 1], n - 1)){
return true;
}
else return packet(s,n - 1);
当然会遇到weight[m]相邻的前面一个物件不是被选择的行列,那么跳过此物件再作判断。
代码
#include<iostream>
using namespace std;
int weight[1005];
bool packet(int s,int n){
if(s == 0) return true;
if(s < 0 ||(s > 0 && n < 1)){
return false;
}
if(packet(s - weight[n - 1], n - 1)){
return true;
}
else return packet(s,n - 1);
}
int main(){
int s, n;
while(cin>>s>>n){
for(int i = 0; i < n; i++){
cin>>weight[i];
}
if(packet(s,n))
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
登录后发布评论
暂无评论,来抢沙发