P1064 金明的预算方案-白红宇

P1064 金明的预算方案

阅读量：4458 次

发布时间：2019-06-08

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

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过

主件附件

电脑打印机，扫描仪

书柜图书

书桌台灯，文具

工作椅无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有

设第 $jj件物品的价格为v_[j]v[j]，重要度为w_[j]w[j]，共选中了kk件物品，编号依次为j_1,j_2,…,j_kj1,j2,…,jk，则所求的总和为：$

$v_[j_1] \times w_[j_1]+v_[j_2] \times w_[j_2]+ …+v_[j_k] \times w_[j_k]v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk]。$

请你帮助金明设计一个满足要求的购物单。

输入输出格式

输入格式：

第

输出格式：

一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（

$有附属关系的背包问题$

$还好这题最多两个附属品那么就是五种状态转移$

$不选只选主件主件加附件1 主件加附件2 主件加所有附件$

$注意要大于体积才能转移！！因为这个wa了$

#include
      
       using namespace std;//input#define rep(i,x,y) for(int i=(x);i<=(y);++i)#define RI(n) scanf("%d",&(n))#define RII(n,m) scanf("%d%d",&n,&m);#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)#define RS(s) scanf("%s",s)#define LL long long#define REP(i,N)  for(int i=0;i<(N);i++)#define CLR(A,v)  memset(A,v,sizeof A)//#define N 65#define inf -0x3f3f3f3fint zhuv[N];int zhuc[N];int fuv[N][3];int fuc[N][3];int dp[32005];int main(){  int m,n;  RII(m,n);  rep(i,1,n)  {      int a,b,c;      RIII(a,b,c);      if(!c)      {          zhuv[i]=a;          zhuc[i]=a*b;      }      else      {          fuv[c][0]++;          fuv[c][fuv[c][0]]=a;          fuc[c][fuv[c][0]]=a*b;      }  }  rep(i,1,n)  for(int j=m;zhuv[i]&&j>=zhuv[i];--j)  {      dp[j]=max(dp[j],dp[j-zhuv[i] ]+zhuc[i] );         if(j>=zhuv[i]+fuv[i][1])      dp[j]=max(dp[j],dp[j-zhuv[i]-fuv[i][1] ]+zhuc[i]+fuc[i][1]      );         if(j>=zhuv[i]+fuv[i][2])       dp[j]=max(dp[j],dp[j-zhuv[i]-fuv[i][2] ]+zhuc[i]+fuc[i][2]     );          if(j>=zhuv[i]+fuv[i][1]+fuv[i][2])      dp[j]=max(dp[j],dp[j-zhuv[i]-fuv[i][1]-fuv[i][2] ]+zhuc[i]+fuc[i][1] +fuc[i][2]      );  }  cout<

View Code

但是很多情况下状态转移不止这几种

得使用背包九讲里面的普适方法！！！

可以先对每种主件的附件的集合进行一次

对于每一种主件的01背包处理：

for i：主件k的所有附件    for j：价值（0 ~ n-主件价值）        01背包递推

这样可以得到主件 $\sim n-v[k]0∼n−v[k] 时的相应最大价值 f[0 \sim n-v[k]]f[0∼n−v[k]]，那么我们就得到了主件 kk 及其附件集合的 n-v[k]+1n−v[k]+1 种不同选择情况，其中费用为 v[k]+tv[k]+t 的物品的价值就是 f[t]+v[k]*p[k]f[t]+v[k]∗p[k] 。$

对于每一个主件处理出的情况，在

如果你不知道分组背包的话：

for 所有的组k    for v = V ... 0        for 所有的i属于组k            f[v]=max{f[v],f[v-c[i]]+w[i]}

这题的分组背包部分应该是这样写的：

for 所有的主件数k    for j = n ... 0        for 所有的主件和附件的组合属于组k            f[j]=max{f[j],f[j-v[i]]+v[i]*p[i]}

#include
      
       using namespace std;//input#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define RI(n) scanf("%d",&(n))#define RII(n,m) scanf("%d%d",&n,&m);#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)#define RS(s) scanf("%s",s);#define LL long long#define REP(i,N)  for(int i=0;i<(N);i++)#define CLR(A,v)  memset(A,v,sizeof A)//#define N 100struct{    int v,c;    int id;}a[N],fu[N][N];//fu为主件i的第j个附件int num[N];//附件个数int c[N][N];//第i组第j个物品的价值int v[N][N];int dp[32000];int cnt[N];//第i组有几个状态int main(){    int n,m;    RII(m,n);    rep(i,1,n)//读入数据   储存到结构体里    {        RIII(a[i].v,a[i].c,a[i].id);        a[i].c*=a[i].v;        if(a[i].id)        {            num[ a[i].id ]++;            fu[ a[i].id ][ num[ a[i].id ] ].v=a[i].v;            fu[ a[i].id ][ num[ a[i].id ] ].c=a[i].c;            fu[ a[i].id ][ num[ a[i].id ] ].id=a[i].id;        }    }        rep(i,1,n)//开始对组的处理    {        if(num[i])//不是主件        {            CLR(dp,-1);//恰好背包初始化            dp[0]=0;//恰好背包                        rep(j,1,num[i])            for(int k=m-a[i].v;k>=fu[i][j].v;k--)                if(dp[k-fu[i][j].v ]!=-1)//注意恰好背包                 dp[k]=max(dp[k],dp[k-fu[i][j].v ]+fu[i][j].c);            rep(j,0,m-a[i].v)//储存每组的所有情况            if(dp[j]!=-1)//恰好背包的判断  这种附件组合满足题意            {                cnt[i]++;                v[i][cnt[i] ]=j+a[i].v;                c[i][cnt[i] ]=dp[j]+a[i].c;            }        }        if(!a[i].id)//如果是主件   该组只有一个        {            cnt[i]++;            v[i][cnt[i] ]=a[i].v;            c[i][cnt[i] ]=a[i].c;        }    }        CLR(dp,0);        rep(i,1,n)        for(int j=m;j>=0;j--)//第几组        rep(k,1,cnt[i])//背包容量        if(j>=v[i][k])//该组第几个状态        dp[j]=max(dp[j],dp[j-v[i][k]]+c[i][k] );        int maxx=0;        rep(i,0,m)        maxx=max(maxx,dp[i]);        cout<

View Code

转载于:https://www.cnblogs.com/bxd123/p/10505436.html

你可能感兴趣的文章