HDU 1712 ACboy needs your help(包背包)

pid=1712">http://acm.hdu.edu.cn/showproblem.php?

pid=1712

题意:

小杰有m天的时间去上n门不同的课. 对于第i门课来说, 假设小杰花j天的时间在该课上, 那么小杰能够获得val[i][j]的价值. 如今给出矩阵val[n][m], 要你求出小杰能获得的最大价值和?

分析:

咋一看, n门课, m天的时间, 要我们求最大价值. 那么明显是从n门课中选出合适的几门, 是的总花费的时间<=m的前提下, 价值最大化. 可是发现每门课有m种不同的价值获取方式.

所以我们换一种问题描写叙述方式: 有n组物品, 每组物品有m个且每组物品中最多仅仅能选1个物品. 第i组物品的花费分别为1 2 3 …m, 第i组物品的价值分别为val[i][1], val[i][2]…val[i][m]. 如今问你初始金钱为m时, 通过上面n组物品, 最多能获得多少价值的物品?

上面问题就是一个明显的分组背包问题了. 我们令dp[i][j]==x表示仅仅选前i组物品且总花费<=j时, 能获得的最大价值为x.

初始化: dp全为0.

状态转移: dp[i][j] == max( dp[i-1][j] , dp[i-1][j-cost[k]]+val[k])

当中cost[k]和val[k]指的是第i组物品的第k个物品的花费和价值.

上面公式前者表示第i组物品一个都不选, 后者表示第i组物品选1个.

终于所求: dp[n][m]的值.

注意: dp递推的3层循环的相互顺序不能改变, 否者会错.(能够自己想一想为什么是这种循环顺序).程序用的滚动数组, dp仅仅有一维.

AC代码:

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=100+5;

int n;//n组物品

int m;//初始金钱数和每组中物品数目

int cost[maxn][maxn];

int val[maxn][maxn];

int dp[maxn];

int main()

{

    while(scanf("%d%d",&n,&m)==2 && n)

    {

        //读取输入

        for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

        {

            scanf("%d",&val[i][j]);

            cost[i][j]=j;

        }

        //递推过程

        memset(dp,0,sizeof(dp));

        for(int i=1;i<=n;i++)//第i组

        for(int j=m;j>=0;j--)//<=j花费时

        for(int k=1;k<=m;k++)//第i组的第k个物品

        {

            if(j>=cost[i][k])

                dp[j] = max(dp[j], dp[j-cost[i][k]]+val[i][k]);

        }

        //输出结果

        printf("%d\n",dp[m]);

    }

    return 0;

}