NOJ-1004：01背包问题-西工大算法

#include <stdio.h>
#include <stdlib.h>

int n, c;
int value[150], weight[150];
int flag[150];
int maxValue, curValue, curWeight;

void inPut();
void dfs(int i);

int main()
{
    int i;
    while(1)
    {
        scanf("%d%d", &n, &c);
        if(n == c && n == 0) break;
        for(i = 1; i <= n; i++)
        {
            scanf("%d", &(weight[i]));
        }
        for(i = 1; i <= n; i++)
        {
            scanf("%d", &(value[i]));
        }
        dfs(1);
        printf("%d\n", maxValue);
        maxValue = 0;
    }
    return 0;
}

void inPut()
{
    scanf("%d%d", &n, &c);
    int i;
    for(i = 1; i <= n; i++)
    {
        scanf("%d", &(weight[i]));
    }
    for(i = 1; i <= n; i++)
    {
        scanf("%d", &(value[i]));
    }
    dfs(1);
    printf("%d\n", maxValue);
}

void dfs(int i)
{
    if(i == n + 1)
    {
        return;
    }
    {
        flag[i] = 0;
        dfs(i + 1);
    };
    {
        if(c >= weight[i] + curWeight)
        {
            flag[i] = 1;
            curValue += value[i];
            curWeight += weight[i];
            if(maxValue < curValue)
            {
                maxValue = curValue;
            }
            dfs(i + 1);
        }
    };
    if(flag[i])
    {
        curValue -= value[i];
        curWeight -= weight[i];
    }
}