首页 > 代码库 > HDU_2079_(01背包)(dfs)
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门。
每组数据的第一行是两个整数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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。