简单背包问题的递归C++算法?

Question

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

Answer 1

#include<stdio.h>#define&nbsp;MAXN 1000int s[MAXN],n;bool dp[MAXN];void dfs(int m,int from){int i;if(dp[m])return ;for(i=from;i<n;i++)//如果物品可以多次去from都重0开始{if(m>=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<n;i++)scanf("%d",&s[i]);dfs(m,0);if(dp[m])printf("存在选择");elseprintf("不存在");return 0;}没有编译器不知道效果怎么样，思路是没错的了