首页 > 代码库 > HDU_2079_(01背包)(dfs)

HDU_2079_(01背包)(dfs)

2024-09-04 00:19:40   219人阅读

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

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[10],num[10],dp[45],n;

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


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

 

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

int cost[10],num[10],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=0;i<=num[index];i++)
    {
        dfs(index+1,sum+i*cost[index]);
    }
}

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

 

HDU_2079_(01背包)(dfs)


联系
我们