Time Limit: 1 second
Memory Limit: 128 MB【问题描述】
黑暗游戏中，装备直接决定玩家人物的能力。可以使用Pg和Rune购买需要的物品。暗黑市场中的装备，每件有不同的价格(Pg和Rune）能力值、最大可购买件数。Kid作为黑暗战网的一个玩家，当然希望使用尽可能少的pg和Rune购买更优的装备，以获得最高的能力值。【输入格式】
第一行，三个整数N,P,R，分别代表市场中物品种类，Pg的支付能力和Rune的支付能力。
第2..n+1行，每行四个整数，前两个整数，前两个整数分别为购买此物品需要花费的Pg，Rune，第三个整数若为0，则说明此物品可 以购买无数件，若为其他数字，则为此物品可购买的最多件数 对于100%的数据，0＜n≤150,0＜P≤100,0＜R≤100,0≤s≤32 样例解释：选第二种装备2件和第三种装备1件。【输出格式】
仅一行，一个整数，最大可获得的能力值。
Sample Input
3 10 105 3 0 1104 3 4 1202 3 1 130
Sample Output
370
【题解】
这是二维费用，混合背包。
用f[i][j]表示费用1不超过i，费用2不超过j所能得到的最大能力值。
最后输出f[m1][m2]就可以了。
f[i][j] = max(f[i][j],f[i-k*w1[m]][j-k*w2[m]] + k*c[m]);
因为是多重背包，与0/1背包类似。逆序更新。
num == 0就用完全背包的做法，顺序更新。f[i][j] = max{f[i][j],f[i-w1[m]][j-w2[m]]+c[m]}
【代码】
#include#include int n,mw1,mw2,w1[200],w2[200],num[200],c[200],f[150][150];void input_data(){ scanf("%d%d%d",&n,&mw1,&mw2); for (int i = 1;i <= n;i++) scanf("%d%d%d%d",&w1[i],&w2[i],&num[i],&c[i]); //输入两种花费的最大限度 }void get_ans(){ memset(f,0,sizeof(f)); for (int i = 1;i <= n;i++) { if (num[i] == 0) //二维费用的完全背包 for (int j = w1[i];j<=mw1;j++) for (int k = w2[i];k <= mw2;k++) //完全背包则一个一个物品更新即可。 if (f[j][k] < f[j-w1[i]][k-w2[i]] + c[i]) f[j][k] = f[j-w1[i]][k-w2[i]] + c[i]; if (num[i] > 0) //二维费用的多重背包。 for (int j = mw1;j >=0;j--) for (int k =mw2;k >= 0;k--) for (int l = 1;l <= num[i];l++) //枚举数目这一层一定要放在枚举容量那一层循环后面 { if (j-l*w1[i] < 0) break; if (k-l*w2[i] < 0) break; //如果超过了容量则跳过 if (f[j][k] < f[j-l*w1[i]][k-l*w2[i]] + l*c[i]) //否则尝试更新 f[j][k] = f[j-l*w1[i]][k-l*w2[i]] + l*c[i]; } }}void output_ans(){ printf("%d",f[mw1][mw2]);}int main(){ //freopen("F:\\rush.txt","r",stdin); input_data(); get_ans(); output_ans(); return 0;}