HDOJ1712

最近补题补得有点惨，发现所谓的会写的题以前看过题解的题只要是自己做的话，永远都做不对

所以每次做完一道错题写完一道AC的代码之后都得水一发博客，下次也能记得在哪

分组背包第一题：分组背包

题意：有n门课程m天，矩阵a[i][j]为在第i门课程上花费j天能够获得的价值。现在m天求最大可以收获的价值

本质上是01背包：哪些选择哪些不选

可是细节上有不同：选择的课程中哪些科目花费多少天，这些都是需要制定的

定义二维：dp【i】【j】为在前i门课程中，花费一共j天的最大价值，那么需要由前i-1天的值推出，所以需要知道第i门课程花费了多少天（不得超过最价值的天数，同理可以不要第i门课程，即花费0天）

dp【i】【j】=max{dp【i】【j】，dp【i-1】【j】，dp【i-1】【j-k】+a【i】【k】}

其中呢：

dp【i】【j】表示跟之前算过的所有值做比较取最大

dp【i-1】【j】表示不需要第i门课程

dp【i-1】【j-k】+a【i】【k】在第i门课程上花费了k天，前i-1门课程花费j-k天

因此需要3重循环，而且上下限已定：由于本质是01背包，一定记得j的顺序（逆序，否则变成完全背包）

代码如下：

int n,m;
int dp[maxn][maxn];
int a[maxn][maxn];

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

01背包可以简化到一维，同理分组背包：dp【j】花费j天的最大价值

定义好了之后，注意这个细节：

只有两种情况，选择（dp[j]+a[i][k]）或者不选择(dp[j]) 
因为在当前层循环之前，数组的值就是所有的不取
第i个没循环到的时候把第i个不取的已经算好了

代码如下：

int main()  
{  
    //freopen("in.txt","r",stdin);  
    int n,m,i,j,k;  
    while(cin>>n>>m)  
    {  
        if(n==0&&m==0)  
            break;  
        memset(dp,0,sizeof(dp));  
  
        //输入部分  
        for(i=1;i<=n;i++)  
            for(j=1;j<=m;j++)  
                cin>>a[i][j];  

        for(i=1;i<=n;i++)  
            for(j=m;j>=0;j--)  
                for(k=j;k<=m;k++)  
                        dp[j]=max(dp[j],dp[j-k]+a[i][k]);  
        cout<<dp[m]<<endl;  
    }  
    return 0;  
}

注意分组背包的实质是01背包，就能够理解为什么会要多一重循环：

01背包是当前物品取或不取，只有两种状态

分组背包是取或者不取，但是取，怎么取，取多少，仍然需要一个循环来枚举