hdu 3033 分组背包（反分组背包）-白红宇的个人博客

hdu 3033 分组背包（反分组背包）

发布日期：2022-03-30 18:18:25 浏览次数：43 分类：博客文章

本文共 1361 字，大约阅读时间需要 4 分钟。

题意：

　　3 5 3

　　1 2 5

　　2 2 1

　　3 2 2

　　第一行有3个数：n v k n 表示有n个物品，v 表示背包容量为v，k表示物品被划分为k类

　　接下来有n行每一行有三个数 a b c a 表示该物品属于第a类，b表示该物品的费用，c表示该物品的价值

　　满足以下条件：1：每个物品最多能拿一次（即01背包） 2：每个类的物品至少拿一个（反分组背包）！！

　　求满足条件的最大价值！！若无输出 Impossible

分析：

　　每组都进行01背包

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

　　 ( 对于第i组物品第j个物品）有

　　dp[i][k] = max{ dp[i][k] , max{ dp[i][k-b[i][j].v]+b[i][j].w , dp[i-1][k]+b[i][j].w} }

#include 
    
     #include 
     
      #include 
      
       using namespace std;int d[11][100001];int x[11];struct Node{    int v,w;}p[11][101];int max(int a,int b){    return a>b ? a : b;}int main(){    int n,v,k,l,ans;    while(~scanf("%d %d %d",&n,&v,&k))    {        memset(d,99999,sizeof(d));        ans=d[0][0]=0;        memset(x,0,sizeof(x));        for(int i=0;i
       
        =p[0][j].v;c--)                d[0][c]=max(d[0][c],d[0][c-p[0][j].v]+p[0][j].w);        d[0][0]= d[0][0]==0? -99999999 : d[0][0];        /*            这一句很关键 网上有很多代码 WA 在这一句            其意思是 只要第一行 没有费用为0 价值大于0 的物品 那么第一行的空背包是不可行的一个解            那么我们就给它 赋值为 - ∞ 。        */        for(int i=1;i
        
         =p[i][j].v;c--)                    d[i][c]=max(d[i][c],max(d[i][c-p[i][j].v]+p[i][j].w,d[i-1][c-p[i][j].v]+p[i][j].w));for(int i=0;i<=v;i++)            ans = max(ans,d[k-1][i]);        if(ans>0)            printf("%d\n",ans);        else            puts("Impossible");    }    return 0;}

转载地址：https://www.cnblogs.com/codeloveme/archive/2012/08/18/2645089.html 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：ST算法

下一篇：hdu 4288 线段树（离散化的离线算法）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章