首页 > 代码库 > 小偷的背包(0963)

小偷的背包(0963)

2024-09-15 16:57:33   220人阅读

<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)


联系
我们