比基础的多一点东西的背包问题。

链接：

大意：有N种砖，每种花费p[i]，含铜量c[i]，现需要用M种不同的砖融成含铜量在Cmin到Cmax之间（可等于）的砖，即这M种砖的含铜量平均值在这个范围内，求最小花费。（M、Cmin、Cmax有多种需求，分别输出花费）

题解：

DP，

f[i][j]表示选i种砖，含铜量的和为j时的最小花费。这样在询问M、Cmin、Cmax之前，先将各种砖数、组成各种含铜量的花费都算好。

DP方程：f[k][j]=min(f[k][j],f[k-1][j-c[i]]+p[i])

方程其实比较容易，主要是外面的循环比较难想……

先将f全部置为inf，然后：

1         f[0][0]=0;///用0个组成0只用0元2         int nn=min(n,20);///种类数的最大值3         for(i=1; i<=n; i++) {
   ///第几个4             for(k=min(i,nn); k>0; k--) ///用的种类数（逆着来防止自身影响5                 for(j=c[i]; j<=mc; j++) {
   ///组成的含量和6                     f[k][j]=min(f[k][j],f[k-1][j-c[i]]+p[i]);///用k种组成含铜总量j的花费7                 }8         }

1.为什么第几块砖放在最外层？把代表种类数的k变量放在最外层不行吗？

当然是不行的！这样各块砖会互相影响，根本没办法好好DP，必须一块一块来。

2.为什么种类数k要逆着来？

正着来会把自己刚刚算好的花费用上，也就相当于用了多次同一块砖，逆着来就不会，因为n种砖的信息不会被n+1种砖的信息影响。（如果是完全背包，也就是一种能用多次，这个就能正着来）

 

这个算完后，读取需求方案，从f[m][m*cmin~m*cmax]中找到最小值，如果最小值是inf就是无解。

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include