HDU1712 ACboy needs your help（分組背包）

題目大意：

       一個人在M天中完成N門課程，每門課程的分數和所用的時間有關系，求解如何安排學習得分最高。

     輸入：兩個整數N和M，接下來是使一個N*M的矩陣A。A[i][j]代表用j天學習第i門課程的分數。

    輸出：得到的最大分數。

解題思路：

       每門作業i隻能選擇一個對應的天數來完成，也就是矩陣的每一行中至多之能選擇一個數，典型的分組背包問題：

分組背包：

有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。這些物品被劃分為若幹組，每組中的物品互相沖突，最多選一件。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

算法

這個問題變成了每組物品有若幹種政策：是選擇本組的某一件，還是一件都不選。也就是說設f[k][v]表示前k組物品花費費用v能取得的最大權值，則有：

f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i屬于組k}

使用一維數組的僞代碼如下：

for 所有的組k

    for v=V..0

        for 所有的i屬于組k

            f[v]=max{f[v],f[v-c[i]]+w[i]}

其中 for v=V..0一定要在 for 所有的i屬于組k之外，否則會出錯。。。。。

是以，得到該問題的狀态轉移方程為：dp[k]=max{dp[k],dp[k-j]+A[i][j]} （dp[k]表示剩餘天數為k時能得到的最大分數）

代碼如下：

# include <iostream>
using namespace std;

int a[102][102],dp[102];

int main()
{
	freopen("input.txt","r",stdin);
	int n,m;
	while(scanf("%d %d",&n,&m)!=EOF && m!=0 && n!=0)
	{
		if(n==0 && m==0) return 0;
		memset(dp,0,sizeof(dp));
		int i,j,k;
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				scanf("%d",&a[i][j]);
		for(i=1;i<=n;i++)
			for(k=m;k>=0;k--)
				for(j=1;j<=k;j++)
				{
					if(dp[k]<dp[k-j]+a[i][j])
						dp[k]=dp[k-j]+a[i][j];
				}
		printf("%d\n",dp[m]);
	}
	return 0;
}