背包问题

/**

Description

设有一个背包可以放入物品的重量为s，现有n件物品，重量分别为w[0],w[1],...,[n-1]。

问题是能否从这n件物品中选择若干件放入此背包中使得放入的重量之和正好等于s。

如果存在一种符合上述要求的选择，则称此背包问题有解；否则称此背包问题无解。

数据输入：

第一行：测试集合个数m。

第二行：第一个测试用例的s值。

第三行：第一个测试用例的物品数量n。

第四行：第一个测试用例的n件物品的重量，中间用空格分开。

第五行：第二个测试用例的s值。

第六行：第二个测试用例的物品数量n。

第七行：第二个测试用例的n件物品的重量，中间用空格分开。

………

第2m行：第m个测试用例的s值。

第2m＋1行：第m个测试用例的物品数量n。

第2m＋2行：第m个测试用例n件物品的重量，中间用空格分开。

数据输出：

第一行到第m行：分别输出是否成功，如果可以放入和为s的物品，则输出1，否则输出0。

Sample Input

2

21

5

2 5 9 11 13

13

4

2 3 5 8

Sample Output

0

1

*/

#include<stdio.h>
#include<stdlib.h>
#define MAX 100

typedef struct
{
    int *base;  //指向栈底
    int *top;   //指向栈顶的后一个
    int sum;    //计算入栈的各数之和
} stack;

void init(stack *s);
void push(stack *s,int data);
void pop(stack *s);

int main()
{
    /**
    cases个测试用例、背包容量为capacity、n为物品数目、weight表示每个物品的重量
    */
    int cases,capacity,n,weight[MAX],i,j;

    scanf("%d",&cases);

    stack *s = (stack*)malloc(sizeof(stack));

    while(cases--)
    {
        scanf("%d",&capacity);
        scanf("%d",&n);

        init(s);

        for(i=0; i<n; i++)
        {
            scanf("%d",&weight[i]);
        }

        for(i=0; i<n; i++)
        {
            for(j=i; j<n; j++)
            {
                if(weight[j] + s->sum <= capacity)  //判断是不是符合入栈条件
                {
                    push(s,weight[j]);
                    if(s->sum == capacity)
                    {
                        printf("1\n");
                        break;
                    }
                }
            }

            if(s->sum == capacity)
            {
                break;
            }
            init(s);
        }

        if(n == i)    //能满足这个条件必定有s->sum != capacity
        {
            printf("0\n");
        }

    }
    return 0;
}



//初始化栈
void init(stack *s)
{
    s->base = s->top = (int*)malloc(MAX * sizeof(int));
    s->sum = 0;
}

//入栈操作
void push(stack *s,int data)
{
    *(s->top) = data; //栈顶元素赋值为data
    (s->top)++;       //始终指向栈顶元素的下一个元素位置
    s->sum += data;   //和要发生变化
}

//出栈操作

void pop(stack *s)
{
    (s->top)--;
    s->sum -= *(s->top);
}