算法：poj 2642 The Brick Stops Here（01背包）

算法：poj 2642 The Brick Stops Here（01背包）2014-01-10 csdn shuangde800题目大意：

黄铜砖是由铜和锌两种元素组成的，每一块黄铜砖中1000克，铜占其中的1～999克之间。铜占比重不同的黄铜砖是属于不同类的。有N个黄铜砖，给出它们的铜占的重量以及价格。

现在有c个客户，每个可以要买Mi个不同类的黄铜砖，要求把Mi个黄铜砖融化后，铜站的比率为每千克在【CMin，CMax】克之间。

问每个客户最少花多少钱可以满足要求？

分析：

f [i][j][k], 代表在前i个砖中，买j个砖，重量为小于等于k的情况下，所花的最少价钱。
状态转移： f[i][j][k] = min（f[i][j][k], f[i-1][j][k], f[i-1][j-1][k-cost[i]]+val [i]）
但是三维耗费空间太大，所以要压缩空间变成二维的
根据背包九讲，在递推时，变成逆序的即可。

代码：

#include<iostream>#include<queue>#include<cstdio>#include<cstring>#include<cmath>#define MP make_pair#define SQ（x） （（x）*（x））using namespace std;typedef long long int64;const double PI = acos（-1.0）;const int MAXN = 210;const int INF = 0x3f3f3f3f;int n, m, copper[MAXN], price[MAXN];int M[MAXN], CMin[MAXN], CMax[MAXN];int f[22][20010];int main（）{while（~scanf（"%d", &n））{for（int i=0; i<n; ++i）scanf（"%d%d", &copper[i], &price[i]）;scanf（"%d", &m）;int max_M = 0, max_weight=0;for（int i=0; i<m; ++i）{scanf（"%d%d%d", &M[i], &CMin[i], &CMax[i]）;if（M[i] > max_M） max_M=M[i];if（CMax[i]*M[i] > max_weight） max_weight = CMax[i]*M[i];}memset（f, INF, sizeof（f））;f[0][0] = 0;for（int i=0; i<n; ++i）{for（int j=max_M; j>=1; --j）{for（int v=max_weight; v>=copper[i]; --v）{f[j][v] = min（f[j][v], f[j-1][v-copper[i]]+price[i]）;}}}for（int i=0; i<m; ++i）{int minx = INF;for（int j=CMin[i]*M[i]; j<=CMax[i]*M[i]; ++j）if（f[M[i]][j] < minx） minx = f[M[i]][j];if（minx == INF） puts（"impossible"）;else printf（"%d
", minx）;}}return 0;}