蓝桥杯算法提高促销购物(动态规划+完全背包)

/问题描述
　　张超来到了超市购物。
　　每个物品都有价格，正好赶上商店推出促销方案。就是把许多东西一起买更便宜（保证优惠方案一定比原价便宜）。物品要买正好的个数，而且不能为了便宜而买不需要的物品。
　　张超拿到了优惠方案，和需要购买的物品清单，当然想求出最小的花费。他是信息学选手，自然地想到写个程序解决问题。
输入格式
　　第一行促销物品的种类数（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）。
　　最多购买 55=25 个商品。
输出格式
　　一个整数ans，表示需要花的最小费用
样例输入
2
1 7 3 5
2 7 1 8 2 10
2
7 3 2
8 2 5
样例输出
14
思路： 动态规划 完全背包 变形

#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]);
     for(j=1;j<=sn[i];j++)
      scanf("%ld%ld",&c[i][j],&k[i][j]);
      scanf("%ld",&p[i]);
}
     scanf("%ld",&b);
     for(i=1;i<=b;i++)
     scanf("%ld%ld%ld",&xc[i],&xk[i],&xp[i]);
    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;
    <span class="token keyword">for</span><span class="token punctuation">(</span>j<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>j<span class="token operator">&lt;=</span>sn<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span>
 h<span class="token punctuation">[</span>sbh<span class="token punctuation">[</span>c<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">=</span>k<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>

       <span class="token keyword">for</span><span class="token punctuation">(</span>b1<span class="token operator">=</span>h<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>b1<span class="token operator">&lt;=</span>xk<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>b1<span class="token operator">++</span><span class="token punctuation">)</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span>b2<span class="token operator">=</span>h<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">;</span>b2<span class="token operator">&lt;=</span>xk<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">;</span>b2<span class="token operator">++</span><span class="token punctuation">)</span>
          <span class="token keyword">for</span><span class="token punctuation">(</span>b3<span class="token operator">=</span>h<span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">;</span>b3<span class="token operator">&lt;=</span>xk<span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">;</span>b3<span class="token operator">++</span><span class="token punctuation">)</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span>b4<span class="token operator">=</span>h<span class="token punctuation">[</span><span class="token number">4</span><span class="token punctuation">]</span><span class="token punctuation">;</span>b4<span class="token operator">&lt;=</span>xk<span class="token punctuation">[</span><span class="token number">4</span><span class="token punctuation">]</span><span class="token punctuation">;</span>b4<span class="token operator">++</span><span class="token punctuation">)</span>
              <span class="token keyword">for</span><span class="token punctuation">(</span>b5<span class="token operator">=</span>h<span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">]</span><span class="token punctuation">;</span>b5<span class="token operator">&lt;=</span>xk<span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">]</span><span class="token punctuation">;</span>b5<span class="token operator">++</span><span class="token punctuation">)</span>
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]);
     <span class="token keyword">for</span><span class="token punctuation">(</span>j<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>j<span class="token operator">&lt;=</span>sn<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span>
       h<span class="token punctuation">[</span>sbh<span class="token punctuation">[</span>c<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
 }
ans=dp[xk[1]][xk[2]][xk[3]][xk[4]][xk[5]];
 printf("%ld\n",ans);
return 0;
}