洛谷 P2732 商店购物 Shopping Offers 题解【DP】【背包】
点击量：235
可以说是暴力背包了吧。。。
题目背景
在商店中，每一种商品都有一个价格（用整数表示）。例如,一朵花的价格是 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：21 7 3 52 7 1 8 2 1027 3 28 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;
}
说点什么