Massive Algorithms: HDU 1712 - ACboy needs your help

HDU 1712 - ACboy needs your help

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

ACboy has N courses this term, and he plans to spend at most M days on study.Of course,the profit he will gain from different course depending on the days he spend on it.How to arrange the M days for the N courses to maximize the profit?

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers N and M, N is the number of courses, M is the days ACboy has.
Next follow a matrix A[i][j], (1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j days on ith course he will get profit of value A[i][j].
N = 0 and M = 0 ends the input.

Output

For each data set, your program should output a line which contains the number of the max profit ACboy will gain.

Sample Input

Sample Output


3
4
6

http://www.cppblog.com/Onway/articles/122695.html

可以将每一门课看成一个分组，每门课不同天数的选择看成是分组的物品（显然只能有一个选择），物品的费用即为花费的天数，物品的价值为题中给出的收获。该题中背包容量最大为M。

设dp[x]为前i组物品，在背包容量为x（即费用为x）时的最大价值。则将i从1到N进行过历遍后（第一重循环），dp[m]即为所求。

在这种状态设置中，容易想出以下两种阶段递推方式（以下所述都为第二和第三重循环）：

1，在同一个背包容量中，对不同费用的物品进行枚举比较：

for(j=MAX;j>=1;--j) //背包容量

for(k=1;k<=m;++k) //不同费用的物品

2，在同一费用的物品中，对放在不同背包容量时计算最大价值：（该方式同《背包九讲-分组背包》中的伪代码部分）

for(k=1;k<=m;++k) //不同费用的物品

for(j=MAX;j>=1;--j) //背包容量

1，分析第一种递推方式的正确:

该方式即求在容量为j的背包中，选择哪一个物品可以有最大价值。

看递推方程：dp[j]=max(dp[j],dp[j-c[k]]+w[k]);（其中c[k]为k物品的费用，w[k]为价值），由于递降枚举背包容量，max比较中的dp[j]是由上一组物品决策所得，在这里将被忽略。因为就算不忽略，在本组物品中dp[j]的决策依然要取决于dp[j-c[k]]+w[k]。

而同样由于递降枚举背包容量（第二重循环），dp[j-c[k]]在本组物品中是未进行过决策的，亦即背包容量为j-c[k]时，在本组物品中是没有选择任何物品的，这可以保证对dp[j]决策时，不会多选本组中的物品。

2，分析第二种递推方式的错误：

该方式即求对物品k，放在所有背包中，计算各个最大价值。

同样是递推方程：dp[j]=max(dp[j],dp[j-c[k]]+w[k]);（其中c[k]为k物品的费用，w[k]为价值）。能否保证dp[j-c[k]]在本组中未经决策，就成了该递推方式对错的关键。

由于背包容量的递降枚举在第三重循环，只能保证k物品不会重复选择。对于另一k0物品，当背包容量枚举到j-c[k]的时候，由方程可以有：dp[j-c[k]]=max(dp[j-c[k]],dp[j-c[k]-c[k0]]+w[k0]，亦即dp[j-c[k]]可能在本组中的其他物品中进行过决策。

那么这样就可能导致在一组物品中选择了多件物品。

https://blog.csdn.net/loveyou11111111/article/details/50674854
这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设 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(int i=1;i<=n;i++)
{
for(int j=m;j>=1;j--)
{
for(int k=1;k<=m;k++)
if(j-k>=0)
dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j-k]+a[i][k]); //一维就可以，很好改，我就不改了
}
}
printf("%d\n",dp[n][m]);
}
https://blog.csdn.net/u013480600/article/details/40649797
所以我们换一种问题描述方式: 有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只有一维.

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

https://www.cnblogs.com/00isok/p/9379331.html

这是一个很明显的分组背包问题，将某一门课程花m个不同天数能够得到不同的价值看成是m个有各自花费和价值的物品，然后，又因为根据题意，每一门课程都只能选择一种花费的天数，于是，这道题就被很自然的转化为分组背包问题。

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &arr[i][j]);
                c[i][j] = j;     //记录要花费的天数( 即背包中的体积 )
            }
        }

        int dp[110];
        memset(dp, 0, sizeof(dp));

        for (int k = 1; k <= n; k++)             //第k门课程       （对应分组背包中的组序号）
        {
            for (int v = m; v >= 0; v--)         //总共所花的天数  （对应背包的容量）由于此题每组物品只能取一次，所以逆序
            {
                for (int i = 1; i <= m; i++)     //第k门课中序号为i的物品    
                {
                    if (v - i < 0)continue;
                    dp[v] = max(dp[v], dp[v - c[k][i]] + arr[k][i]);
                }
            }
        }      //dp[i][j]为，前i组中花费天数为v时，所能得到的最大价值

https://blog.csdn.net/u012860063/article/details/34107953

题意：一开始输入n和m，n代表有n门课，m代表你有m天，
然后给你一个数组，val[i][j]，代表第i门课，在通过j天去修，
会得到的分数。求在m天能得到的最大分数。

while(~scanf("%d%d",&n,&m)&&( n || m))
{
memset(dp,0,sizeof(dp));
for(i = 1; i <=n ; i++)
{
for(j = 1; j <= m ;j++)
scanf("%d",&a[i][j]);
}
for(i = 1 ; i <= n ; i++)//第一重循环：分组数
{
for(j = m ; j >= 1 ; j--) //第二重循环：容量体积
{
for(k = 1 ; k <= j ; k++) //第三重循环：属于i组的k
{
dp[j]=max(dp[j],dp[j-k]+a[i][k]);
}
}
}
printf("%d\n",dp[m]);
}

http://blog.sina.com.cn/s/blog_79b832820100rfpc.html
    for (i=0;i<n;i++)
        for (j=m;j>=1;j--)     //第二重循环和第三重循环不能交换，否则变成了一个课程可以用不同天多次完成。
            for (k=1;k<=j;k++)
                f[j]=max(f[j],f[j-k]+v[i][k]);

    return f[m];

HDU 1712 - ACboy needs your help

Labels

Popular Posts