HDU_2079_(01背包)(dfs)

选课时间(题目已修改,注意读题)

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4478    Accepted Submission(s): 3480

Problem Description

又到了选课的时间了，xhd看着选课表发呆，为了想让下一学期好过点，他想知道学n个学分共有多少组合。你来帮帮他吧。（xhd认为一样学分的课没区别）

Input

输入数据的第一行是一个数据T，表示有T组数据。
每组数据的第一行是两个整数n(1 <= n <= 40)，k(1 <= k <= 8)。
接着有k行，每行有两个整数a(1 <= a <= 8),b(1 <= b <= 10)，表示学分为a的课有b门。

Output

对于每组输入数据，输出一个整数，表示学n个学分的组合数。

Sample Input

2

2 2

1 2

2 1

40 8

1 1

2 2

3 2

4 2

5 8

6 9

7 6

8 8

Sample Output

2

445

最开始用多重背包做，发现二进制优化多出的零头可能发生重复，但是没相处解决方案。

看题解用的01背包，稍作修改避免了重复。

因为数据规模小，用dfs也很方便。

01背包：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int cost[],num[],dp[],n;

void zero_one(int cost,int num)
{
    for(int j=n;j>=cost;j--)
        for(int k=;k<=num&&j-k*cost>=;k++)
            dp[j]+=dp[j-cost*k];
}

int main()
{
    int t,k;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,,sizeof(dp));
        dp[]=;
        scanf("%d%d",&n,&k);
        for(int i=;i<k;i++)
        {
            scanf("%d%d",&cost[i],&num[i]);
            if(cost[i]*num[i]>n)
                num[i]=n/cost[i];
            //dp[cost[i]]=1;
        }
        for(int i=;i<k;i++)
        {
            zero_one(cost[i],num[i]);
        }
        printf("%d\n",dp[n]);
    }
    return ;
}

dfs：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int cost[],num[],res,n,k;

void dfs(int index,int sum)
{
    if(index>k||sum>n)
        return;
    if(index==k&&sum!=n)
        return;
    if(sum==n)
    {
        res++;
        return;
    }
    for(int i=;i<=num[index];i++)
    {
        dfs(index+,sum+i*cost[index]);
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        res=;
        scanf("%d%d",&n,&k);
        for(int i=;i<k;i++)
            scanf("%d%d",&cost[i],&num[i]);
        dfs(,);
        printf("%d\n",res);
    }
    return ;
}