DFS之简单背包问题

#简单背包问题
题目描述
设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。
问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。
如果有满足条件的选择，则此背包有解，否则此背包问题无解。

输入：
输入数据有多行，包括放入的物品重量为s，物品的件数n，以及每件物品的重量（输入数据均为正整数）
多组测试数据。

输出：
对于每个测试实例，若满足条件则输出“YES”，若不满足则输出“NO”

样例输入：
20 5
1 3 5 7 9
样例输出：
YES

AC代码

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[200],flag[200],s,n,sum;
bool ass=0;
void dfs(int x)
{
if(sum==s)
{
ass=1;//总和恰好等于背包容量，符合条件，退出；
return ;
}
if(x==n+1)
{
return ;//把所有的物品都加起来了仍无法达到总和，退出
}
for(int i=0;i<n;i++)
if(!flag[i])//如果第i件物品没有被加
{
flag[i]=1;//标记该物品为被搜索过
sum+=a[i];
dfs(x+1);//继续向下搜索
sum-=a[i];//退回
flag[i]=0;
}
}
int main()
{
while(cin>>s>>n)
{
memset(flag,0,sizeof(flag));
ass=0,sum=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
dfs(0);
if(ass==1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}

最后

以上就是优美飞鸟为你收集整理的DFS之简单背包问题的全部内容，希望文章能够帮你解决DFS之简单背包问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。