简单背包问题的递归C++算法设有一个背包可以放入的物品的重量为s,现有n件物品,重量分别为w[1],w[2],…,w[n].问能否从这n件物品中选择若干件放入此背包中,使得放入的重量之和正好为s.如果存

简单背包问题的递归C++算法设有一个背包可以放入的物品的重量为s,现有n件物品,重量分别为w[1],w[2],…,w[n].问能否从这n件物品中选择若干件放入此背包中,使得放入的重量之和正好为s.如果存
简单背包问题的递归C++算法
设有一个背包可以放入的物品的重量为s,现有n件物品,重量分别为w[1],w[2],…,w[n].问能否从这n件物品中选择若干件放入此背包中,使得放入的重量之和正好为s.如果存在一种符合上述要求的选择,则称此背包问题有解(或称其解为真)；否则称此背包问题无解(或称其解为假).试用递归方法设计求解背包问题的算法.

简单背包问题的递归C++算法设有一个背包可以放入的物品的重量为s,现有n件物品,重量分别为w[1],w[2],…,w[n].问能否从这n件物品中选择若干件放入此背包中,使得放入的重量之和正好为s.如果存
#include
#define MAXN 1000
int s[MAXN],n;
bool dp[MAXN];
void dfs(int m,int from)
{
int i;
if(dp[m])
return ;
for(i=from;i=s[i])
{
dfs(m-s[i],from+1);
if(dp[m-s[i])
{
dp[m]=true;
break;
}
}
}
}
int main()
{
int i;
memset(dp,false,sizeof(dp));
dp[0]=true;
scanf("%d%d",&n,&m);//个数和要求质量
for(i=0;i