首页 > 代码库 > 小偷的背包(0963)
小偷的背包(0963)
<style>p { margin-bottom: 0.25cm; line-height: 120% }</style>
描述
设有一个背包可以放入的物品重量为S,现有n件物品,重量分别是w1,w2,w3,...,wn。问能否从这n件物品中选择若干件放入背包中,使得放入的重量之和正好为S。如果有满足条件的选择,则此背包有解,否则此背包问题无解。
input
第一行为物品重量S(整数);
第二行为物品数量n,
第三行为n件物品的重量的序列。
output
有解就输出”yes!“,没有解就输出”no!“
样例输入
20
5
1 3 5 7 9
样例输出
yes!
这道题我是通过递归的方式做的,如果最后一次恰好刚好装满则返回1,然后s减掉wn,如果没有则检查wn-1,s不变,最后通过递归返回到开始第一个。
我的代码如下
#include<stdio.h>
int
bagWeight[50];
int
bag(
int
s,
int
n)
{
if
(s==0)
{
return
1;
}
if
(s<0||s>0&&n==0)
{
return
0;
}
if
(bag(s-bagWeight[n],n-1)==1)
{
return
1;
}
return
bag(s,n-1);
}
int
main()
{
int
s;
int
n;
int
i;
int
flag;
while
(
scanf
(
"%d%d"
,&s,&n)!=EOF)
{
for
(i=1; i<=n; i++)
{
scanf
(
"%d"
,&bagWeight[i]);
}
flag=bag(s,n);
if
(flag==1)
{
printf
(
"yes!"
);
}
else
{
printf
(
"no!"
);
}
}
return
0;
}
小偷的背包(0963)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。