設有一個背包可以放入的物品的重量為s，現(xiàn)有n件物品，重量分別為w[1], w[2], …, w[n]。問能否從這n件物品中選擇若干件放入此背包中，使得放入的重量之和正好為s。如果存在一種符合上述要求的選擇，則稱此背包問題有解(或稱其解為真)；否則稱此背包問題無解(或稱其解為假)。試用遞歸方法設計求解背包問題的算法。
1 回答
翻翻過去那場雪
TA貢獻2065條經驗 獲得超14個贊
#include<stdio.h>
#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<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);//個數(shù)和要求質量
for(i=0;i<n;i++)
scanf("%d",&s[i]);
dfs(m,0);
if(dp[m])
printf("存在選擇");
else
printf("不存在");
return 0;
}
沒有編譯器不知道效果怎么樣，思路是沒錯的了
- 1 回答
- 0 關注
- 1056 瀏覽
添加回答
舉報
0/150
提交
取消