HDU 3449 Consumer 依赖背包 入门题

前端之家收集整理的这篇文章主要介绍了HDU 3449 Consumer 依赖背包 入门题前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

题意:有钱sum,给出n组选择,每种选择有m个物品w,要买物品先必须买盒子,物品价格为w[i],价值p[i]。

然后给出每种选择的一些物品的价格还有价值求取得最大值。

物品依赖于盒子。

按照背包九讲的做法:

先对每组选择里的所有物品进行0-1背包处理,但背包容量为(总容量-盒子容量);

然后跟上一组的状态比较来决定这一组选择 是选还是不选,取其中的较大值。

用dp[i][j]表示第i组背包容量为j时的最大价值。

在转移状态之前当前组选择的初始化:

for(j=0;j<q;j++)//q表示盒子的价格
    dp[i][j]=-INF;//当钱<盒子价格时,无价值,注意不要赋值为0, 这题有 重量为0,但有价值的物品。
//例如 这组数据
1 10 11 1 0 11
盒子都买不起,所以输出0
但以上如果赋值为0,程序会输出11,是错误的。
for(j=q;j<=sum;j++) dp[i][j]=dp[i-1][j-q];//当钱>=盒子价格时,让前一组状态先买个盒子,买好盒子之后状态变为dp[i-1][j-q];

二维数组版:

View Code
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define INF 1<<29
int n,sum,m,q;
int w[11],p[11];
int dp[51][100003];
int main()
{
    int i,j,x;
    while(~scanf("%d%d",&n,&sum))
    {
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&q,&m);
            for(x=1;x<=m;x++)
                scanf("%d%d",&w[x],&p[x]);
           //注意初始化,上面已做出解释
            for(j=0;j<=q;j++)
                dp[i][j]=-INF;
            for(j=q;j<=sum;j++)
                dp[i][j]=dp[i-1][j-q];
            //按照背包九讲的做法,将当前组的物品进行0-1背包处理。    
            for(x=1;x<=m;x++)
                for(j=sum;j>=w[x];j--)
                    dp[i][j]=max(dp[i][j],dp[i][j-w[x]]+p[x]);
            //跟上一组的状态进行比较,选择较大的值,
            //如果选dp[i][j]说明选了当前组的物品和盒子,
            //如果选dp[i-1][j]说明没有选当前组的物品和盒子。        
            for(j=0;j<=sum;j++)
                dp[i][j]=max(dp[i][j],dp[i-1][j]);
        }
        printf("%d\n",dp[n][sum]);
    }
    return 0;
}

滚动数组版:

View Code
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define INF 1<<29
int n,q;
int w,p;
int dp[100003],tmp[100003];
int main()
{
    int i,&m);
            for(j=0;j<q;j++)
                tmp[j]=-INF;
            for(j=q;j<=sum;j++)
                tmp[j]=dp[j-q];
            for(x=1;x<=m;x++)
            {
                scanf("%d%d",&w,&p);//写在循环内,边读入边对其进行0-1背包,省去了2个数组
                for(j=sum;j>=w;j--)
                    tmp[j]=max(tmp[j],tmp[j-w]+p);
            }
            for(j=0;j<=sum;j++)
                dp[j]=max(dp[j],tmp[j]);
        }
        printf("%d\n",dp[sum]);
    }
    return 0;
}
原文链接:https://www.f2er.com/javaschema/286057.html

猜你在找的设计模式相关文章