文章

11

粉丝

152

获赞

9

访问

36.0k

头像
动态规划入门 - 简单背包
P1035
发布于2022年7月3日 17:36
阅读数 6.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;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发