本文共 1051 字，大约阅读时间需要 3 分钟。
题目链接：
题目大意：
黄铜砖是由铜和锌两种元素组成的，每一块黄铜砖中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 #include #include #include #include #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 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 =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
转载地址：http://opzni.baihongyu.com/