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

P1064 金明的预算方案

阅读量：6976 次

发布时间：2019-06-27

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

一道有毒的有依赖的背包问题。。。

题目描述

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

主件附件

电脑打印机，扫描仪

书柜图书

书桌台灯，文具

工作椅无

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

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

$v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[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：

1000 5800 2 0400 5 1300 5 1400 3 0500 2 0

输出样例#1：

输入样例#2：

2000 10 500 1 0 400 4 0 300 5 1 400 5 1 200 5 0 500 4 5 400 4 0 320 2 0 410 3 0 400 3 5

输出样例#2：

说明

NOIP 2006 提高组第二题

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int maxx(int x,int y){    return x>y?x:y;}int N,m,f[3200],val[10000],p[10000],q,a[10000][3],pr[10000][3];int main(){    cin>>N>>m;    N/=10;    for(int i=1;i<=m;i++)    {        cin>>val[i]>>p[i]>>q;        val[i]/=10;        if(q)        {            //val[i]=0;    因为这里我这道题多做了3个小时，哭了ToT，低级错误            a[q][++a[q][0]]=val[i];            pr[q][a[q][0]]=p[i]; 　　　　　　　val[i]=0;        }     }        for(int i=1;i<=m;i++)        for(int v=N;val[i]&&v>=val[i];v--)        {        f[v]=maxx(f[v],f[v-val[i]]+val[i]*p[i]);        if(a[i][0]&&val[i]+a[i][1]<=v)        f[v]=maxx(f[v],f[v-val[i]-a[i][1]]+val[i]*p[i]+a[i][1]*pr[i][1]);        if(a[i][0]&&val[i]+a[i][2]<=v)        f[v]=maxx(f[v],f[v-val[i]-a[i][2]]+val[i]*p[i]+a[i][2]*pr[i][2]);        if(a[i][0]&&val[i]+a[i][1]+a[i][2]<=v)f[v]=maxx(f[v],f[v-val[i]-a[i][1]-a[i][2]]+val[i]*p[i]+a[i][1]*pr[i][1]+a[i][2]*pr[i][2]);        }        cout<

转载于:https://www.cnblogs.com/JCRL/p/10049778.html

你可能感兴趣的文章