选课时间(题目已修改,注意读题)
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3162 Accepted Submission(s): 2472
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
我上一个AC的代码：
#include
#include
#define MAX 55 int dp[MAX] ; int main() { int t ; scanf("%d",&t); while(t--) { int n , k ,a,b; scanf("%d%d",&n,&k) ; memset(dp,0,sizeof(int)*(n+10)) ; dp[0] = 1 ; for(int i = 0 ; i < k ; ++i) { scanf("%d%d",&a,&b); for(int j = n ; j >= a ; --j) { for(int x = 1 ; x <= b ; ++x) { if(j>=x*a) dp[j] += dp[j-x*a] ; } } } printf("%d\n",dp[n]) ; } return 0 ; }
上面的代码完全是把多重背包转化为01背包了。
我下面上一份没有AC的代码，，但是我很郁闷，它为什么不能AC！！！求大神指点，先前是用二进制优化的，，错的离谱的不能在离谱，后来转化为用01背包和完全背包时，还是wrong。真的很蛋疼，跪求大神
update：我隐隐约约已经知道为什么了。。
#include
#include
#define MAX 55 int dp[MAX] ; void zeroOnePack(int value , int total) { for(int i = total ; i >= value ; --i) { dp[i] = dp[i] + dp[i-value] ; } } void completePack(int value , int total) { for(int i = value ; i <= total ; ++i) { dp[i] = dp[i] + dp[i-value] ; } } void multiplePack(int value , int count , int total) { if(count*value > total) { completePack(value , total) ; } else { int k = 1 ; while(k<=count) { zeroOnePack(k*value , total); ++k ; } } } int main() { int t ; scanf("%d",&t); while(t--) { int n , k ,a[45],b[45]; scanf("%d%d",&n,&k) ; for(int i = 0 ; i < k ; ++i) { scanf("%d%d",&a[i],&b[i]); } memset(dp,0,sizeof(int)*(n+10)) ; dp[0] = 1 ; for(int i = 0 ; i < k ; ++i) { multiplePack(a[i],b[i],n) ; } printf("%d\n",dp[n]) ; } return 0 ; }