首页 > 代码库 > poj2642 The Brick Stops Here（DP基础题）
poj2642 The Brick Stops Here（DP基础题）
比基础的多一点东西的背包问题。
链接：POJ2642
大意：有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<cstdio> 2 #include<cmath> 3 #include<iostream> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<map> 8 #include<set> 9 using namespace std;10 #define ll __int6411 #define usint unsigned int12 #define mz(array) memset(array, 0, sizeof(array))13 #define minf(array) memset(array, inf, sizeof(array))14 #define REP(i,n) for(int i=0;i<(n);i++)15 #define RE freopen("1.in","r",stdin)16 #define WE freopen("1.out","w",stdout)17 18 const int maxn=200;19 const int maxc=111;20 const int maxcc=1000;21 const int inf=0x3f3f3f3f;22 const int mc=20*maxcc;///最多只要20个合一23 int c[maxn],p[maxn];24 25 int f[maxn][mc];///f[k][j]表示用k个组成总含量j的用钱26 27 28 int main() {29 int n,m,C,cmin,cmax;30 int i,j,k,ans;31 bool flag=false;32 while(scanf("%d",&n)!=EOF) {33 for(i=1; i<=n; i++)34 scanf("%d%d",&c[i],&p[i]);35 scanf("%d",&C);36 minf(f);37 f[0][0]=0;///用0个组成0只用0元38 int nn=min(n,20);///种类数的最大值39 for(i=1; i<=n; i++) {///第几个40 for(k=min(i,nn); k>0; k--) ///用的种类数（逆着来防止自身影响41 for(j=c[i]; j<=mc; j++) {///组成的含量和42 f[k][j]=min(f[k][j],f[k-1][j-c[i]]+p[i]);///用k种组成含铜总量j的花费43 }44 }45 if(flag)puts("");46 for(k=0; k<C; k++) {47 scanf("%d%d%d",&m,&cmin,&cmax);48 int cma=cmax*m;49 ans=inf;50 for(i=cmin*m; i<=cma; i++) {51 ans=min(f[m][i],ans);52 }53 if(ans==inf) printf("impossible\n");54 else printf("%d\n",ans);55 }56 flag=true;57 }58 return 0;59 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。