蓝桥杯 —— 促销购物问题

Question

张超来到了超市购物。每个物品都有价格，正好赶上商店推出促销方案。就是把许多东西一起买更便宜（保证优惠方案一定比原价便宜）。物品要买正好的个数，而且不能为了便宜而买不需要的物品。张超拿到了优惠方案，和需要购买的物品清单，请编程求出最小的花费。
输入
第一行促销物品的种类数（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 个商品。
输出：
一个整数ans，表示需要花的最小费用

1.

#include<stdio.h>
#include<string.h>

 long int bj(long int a,long int b)
 { return a<b?a:b;
 }
int main()
{ long int s,i,j,j1,b,ans=0,dans=0,b1,b2,b3,b4,b5;
  long int sn[101];//sn[i]第i种促销种类的物品数 
   long int c[101][7],k[101][7],p[101],xc[7]={0},xp[7]={0},xk[7]={0};
   long int dp[6][6][6][6][6];//dp[2][3][4][1][0]代表 当前第 1~5 个物品 分别 购2 3 4 1 0 件所需最少钱 
   long h[6]={0};//h[i] 表示 i 号商品促销数量 
   long sbh[1001]={0};//标号表 链接 促销序号和需买序号的桥梁 
 scanf("%ld",&s);                //促销物品的种类数 
 for(i=1;i<=s;i++)               
 {
     scanf("%ld",&sn[i]);          //第i种促销的种类数 (这种促销方式由n种商品成)
     for(j=1;j<=sn[i];j++)            
      scanf("%ld%ld",&c[i][j],&k[i][j]);    //对于该促销方式的商品，每种商品的编号和数量 
      scanf("%ld",&p[i]);                    //该促销的价格 
}
     scanf("%ld",&b);                     //第 s+2 行这行一个整数b （0 <= b <= 5），表示需要购买 b 种不同的商品。
     for(i=1;i<=b;i++)                    
     scanf("%ld%ld%ld",&xc[i],&xk[i],&xp[i]);          //对于b种不同的商品，编号，需要的数量，原价
    for(j=1;j<=b;j++)//初始化需求物品的数量 sbh[i] 代表需求品序号 存 需求数量 
      sbh[xc[j]]=j;                  //（第一个商品需要几个，第二个需要几个） 
            for(b1=0;b1<=xk[1];b1++)
            for(b2=0;b2<=xk[2];b2++)
              for(b3=0;b3<=xk[3];b3++)
                for(b4=0;b4<=xk[4];b4++)
                  for(b5=0;b5<=xk[5];b5++)
                if(b1*xp[1]+b2*xp[2]+b3*xp[3]+b4*xp[4]+b5*xp[5])
                dp[b1][b2][b3][b4][b5]=b1*xp[1]+b2*xp[2]+b3*xp[3]+b4*xp[4]+b5*xp[5];
                  //初始化 原价购买 
                   dp[0][0][0][0][0]=0;
                
 for(i=1;i<=s;i++)
 {   
         for(j=1;j<=sn[i];j++)
    if(xk[sbh[c[i][j]]]<k[i][j])break;//当前促销品 促销量大于需量 或者 促销品不需要 则不能选择此促销种类 
        if(j<sn[i])continue;
    
        for(j=1;j<=sn[i];j++)
     h[sbh[c[i][j]]]=k[i][j];
           
           for(b1=h[1];b1<=xk[1];b1++)
            for(b2=h[2];b2<=xk[2];b2++)
              for(b3=h[3];b3<=xk[3];b3++)
                for(b4=h[4];b4<=xk[4];b4++)
                  for(b5=h[5];b5<=xk[5];b5++)
dp[b1][b2][b3][b4][b5]=bj(dp[b1][b2][b3][b4][b5],dp[b1-h[1]][b2-h[2]][b3-h[3]][b4-h[4]][b5-h[5]]+p[i]);  //比较原价购买和促销价格 ，返回较低值 
    
         for(j=1;j<=sn[i];j++)
           h[sbh[c[i][j]]]=0;   //？？？ 
    
 } 

除了上面的**

• **动态规划，可以用别的算法解决吗

Answer 1

C语言[蓝桥杯][算法提高VIP]促销购物
解题思路：
看到底下的标签是动态规划之后，仔细一想确实可以转换为完全背包问题，但是背包开几维啊，每一维的容量可以表示为所需物品的最大件数，但是物品有999种啊。
这时，我们的突破口就应该放在最多购买5种不同的商品上，这样我们只需要五维就可以控制选的五种商品了。
与经典背包不同这个是求最小值，因此初始化非常关键。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;

struct SALE { // 促销活动的信息 
    int num[N]; // num[i] 表示此促销活动要求买编号为i的商品多少个 
    int p; // 此促销方式的价格 
} sale[N]; // sale[i] 表示第i种促销方式 

struct BUY { // 顾客要买的商品 
    int c, k, p; // 编号、数量、单价 
} buy[6]; // buy[i] 表示要买的第i种商品（并非编号为i的商品）的信息 

int s, n, b, c, k, p;
int ans[6][6][6][6][6]; // ans[i(1)][i(2)][i(3)][i(4)][i(5)] 表示购买i(j)件第j种商品（并非编号为j的商品）的最小花费，其中j=1~5 

int main()
{
    cin>>s;
    for(int i = 1;i <= s;i ++) {
        cin>>n;
        for(int j = 1;j <= n;j ++) cin>>c>>k, sale[i].num[c] = k;
        cin>>sale[i].p;
    }
    cin>>b;
    for(int i = 1;i <= b;i ++) {
        cin>>c>>k>>p;
        buy[i].c = c, buy[i].k = k, buy[i].p = p;
        // 还需要保存每个单件物品，也算是一种促销方式；等价于背包问题中的一类物品 
        sale[++s].num[c] = 1; // 无法用折扣，因此每个商品都按单价算 
        sale[s].p = p;
    }
    
    // 背包问题求最小值的初始化方式 
    memset(ans, 0x3f, sizeof ans);
    ans[0][0][0][0][0] = 0;
    
    for(int i = 1;i <= s;i ++) {
        int m1 = sale[i].num[buy[1].c]; // 在第i种促销方式中，需要一次性买第1个商品（并非编号为1的商品）的数量 
        int m2 = sale[i].num[buy[2].c]; // 在第i种促销方式中，需要一次性买第2个商品（并非编号为2的商品）的数量 
        int m3 = sale[i].num[buy[3].c];
        int m4 = sale[i].num[buy[4].c];
        int m5 = sale[i].num[buy[5].c];
        
        for(int i1 = m1;i1 <= buy[1].k;i1 ++)
        for(int i2 = m2;i2 <= buy[2].k;i2 ++)
        for(int i3 = m3;i3 <= buy[3].k;i3 ++)
        for(int i4 = m4;i4 <= buy[4].k;i4 ++)
        for(int i5 = m5;i5 <= buy[5].k;i5 ++)
        ans[i1][i2][i3][i4][i5] = min(ans[i1][i2][i3][i4][i5], ans[i1-m1][i2-m2][i3-m3][i4-m4][i5-m5] + sale[i].p);
    }
    
    cout<< ans[buy[1].k][buy[2].k][buy[3].k][buy[4].k][buy[5].k] << endl;
    
    return 0;
}