程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu 2079 選課時間(題目已修改,注意讀題) 多重背包

hdu 2079 選課時間(題目已修改,注意讀題) 多重背包

編輯:關於C++

選課時間(題目已修改,注意讀題)

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 ;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved