洛谷 P2732 商店购物 Shopping Offers 题解【DP】【背包】

作者: wjyyy 分类: DP,背包,解题报告 发布时间: 2018-07-01 20:30

点击量:17

 

   可以说是暴力背包了吧。。。

 

题目背景

在商店中,每一种商品都有一个价格(用整数表示)。例如,一朵花的价格是 2 zorkmids (z),而一个花瓶的价格是 5z 。为了吸引更多的顾客,商店举行了促销活动。

题目描述

促销活动把一个或多个商品组合起来降价销售,例如:

 

三朵花的价格是 5z 而不是 6z, 两个花瓶和一朵花的价格是 10z 而不是 12z。 编写一个程序,计算顾客购买一定商品的花费,尽量利用优惠使花费最少。尽管有时候添加其他商品可以获得更少的花费,但是你不能这么做。

 

对于上面的商品信息,购买三朵花和两个花瓶的最少花费的方案是:以优惠价购买两个花瓶和一朵花(10z),以原价购买两朵花(4z)。

 

输入输出格式

输入格式:

输入文件包括一些商店提供的优惠信息,接着是购物清单。(最多有5种商品)

 

第一行 优惠方案的种类数(0<=s<=99)。

 

第二行..第s+1行 每一行都用几个整数来表示一种优惠方式。第一个整数 n(1<=n<=5),表示这种优惠方式由n种商品组成。后面n对整数c和k表示 k(1<=k<=5)个编号为 c(1<=c<=999)的商品共同构成这种优惠,最后的整数p表示这种优惠的优惠价(1 <= p<=9999)。优惠价总是比原价低。

 

第s+2行 这一行有一个整数 b(0<=b<=5),表示需要购买 b 种不同的商品。

 

第 s+3 行..第 s+b+2 行 这 b 行中的每一行包括三个整数:c,k,p。 c 表示唯一的商品编号(1 <= c <= 999),k 表示需要购买的 c 商品的数量(1 <= k <= 5)。p 表示 c 商品的原价(1 <= p <= 999)。最多购买 5*5=25 个商品。

 

输出格式:

只有一行,输出一个整数:购买这些物品的最低价格。

 

输入输出样例

输入样例#1:
2
1 7 3 5
2 7 1 8 2 10
2
7 3 2
8 2 5
输出样例#1:
14

   一开始看到5个物品就打了搜索,结果无法剪枝,只拿了76分,原因是有个贪心贪错了,如果改对,这3个点就会T,如果不改就是WA,最后贴代码。

 

   因为优惠是可以累加的,所以我们考虑完全背包。状态因为只有5×5,所以我们用一个五维的数组来存下状态f[i1][i2][i3][i4][i5],表示当购买ij个j商品时花费的最少钱数。这个过程挺好想的,只不过多种物品混杂在一起,其实状态还是那么多,只要自己处理好就可以了。

 

   这个题用刷表法的话更加简洁,填表法也不是不可以,我这里用的是刷表,通过某个状态去转移其他状态,并控制每个ij都小于j的要购买数量。这样一来,这个空间五维,时间六维的背包就做完了。

 

Code:(76pts的搜索,错误的贪心)

#include<cstdio>
#include<cstring>
#include<algorithm>
struct item
{
    int n,p,k;//p表示价格,c表示买几个
    friend bool operator <(item a,item b)
    {
        return a.n<b.n;
    }
}t[10];
int s[100][1000];
int snxt[100][1000];
int nxt[1000];
int ans=123456789,n,m;
int re[1000],sum=0;
int check(int x)
{
    int r=123456789,tmp;
    for(int i=snxt[x][0];i;i=snxt[x][i])
    {
        tmp=re[i]/s[x][i];
        r=r<tmp?r:tmp;
    }
    return r;
}
void dfs(int x)//x表示找到第几个优惠了
{
    if(sum>ans)
        return;
    //printf("1");
    //找可行的优惠
    for(int i=x;i<=m;i++)
    {
        int k=check(i);
        if(k)
        {
            for(int j=snxt[i][0];j;j=snxt[i][j])
                re[j]-=k*s[i][j];
            sum+=k*s[i][0];
            dfs(i+1);
            sum-=k*s[i][0];
            for(int j=snxt[i][0];j;j=snxt[i][j])
                re[j]+=k*s[i][j];
        }
    }

    //无论如何都计算剩下的价格
    int delta=0;
    for(int i=1;i<=n;i++)
        delta+=re[t[i].n]*t[i].p;
    sum+=delta;
    ans=ans<sum?ans:sum;
    sum-=delta;
    return;
}
int main()
{
    memset(nxt,0,sizeof(nxt));
    memset(snxt,0,sizeof(snxt));
    int u,v,k,w;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&k);
        //s[i][0]=k;
        for(int j=1;j<=k;j++)
        {
            scanf("%d%d",&u,&v);
            s[i][u]=v;
        }
        int lst=0;
        for(int j=1;j<=999;j++)
            if(s[i][j])
            {
                snxt[i][lst]=j;
                lst=j;
            }
        scanf("%d",&s[i][0]);
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        t[i].n=u;
        t[i].k=v;
        t[i].p=w;
        re[u]=v;
    }
    std::sort(t+1,t+1+n);
    nxt[0]=t[1].n;
    for(int i=1;i<n;i++)
        nxt[t[i].n]=t[i+1].n;
    nxt[t[n].n]=0;
    dfs(1);
    printf("%d\n",ans);
    return 0;
}

Code:(正解背包)

#include<cstdio>
#include<cstring>
int min(int x,int y)
{
    return x<y?x:y;
}
int f[8][8][8][8][8];
int Map[1000];//映射
int s[100][15];//方案数
int cnt=0;
int b[8],c[8];
int main()
{
    int m,k,u,v;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&k);
        for(int j=1;j<=k;j++)
        {
            scanf("%d%d",&u,&v);
            if(!Map[u])
                Map[u]=++cnt;
            s[i][Map[u]]=v;
        }
        scanf("%d",&s[i][0]);
    }
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&u);
        if(!Map[u])
            Map[u]=++cnt;
        scanf("%d%d",&b[Map[u]],&c[Map[u]]);
        s[m+i][Map[u]]=1;
        s[m+i][0]=c[Map[u]];
    }
    //backpack
    memset(f,0x3f,sizeof(f));
    f[0][0][0][0][0]=0;
    for(int i=1;i<=m+n;i++)
        for(int i1=0;i1<=b[1];i1++)
            for(int i2=0;i2<=b[2];i2++)
                for(int i3=0;i3<=b[3];i3++)
                    for(int i4=0;i4<=b[4];i4++)
                        for(int i5=0;i5<=b[5];i5++)
                            if(i1+s[i][1]<=b[1]&&i2+s[i][2]<=b[2]&&i3+s[i][3]<=b[3]&&i4+s[i][4]<=b[4]&&i5+s[i][5]<=b[5])
                            {//地址存一下优化常数
                                int &p=f[i1+s[i][1]][i2+s[i][2]][i3+s[i][3]][i4+s[i][4]][i5+s[i][5]];
                                p=min(p,f[i1][i2][i3][i4][i5]+s[i][0]);
                            }
    printf("%d\n",f[b[1]][b[2]][b[3]][b[4]][b[5]]);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */