锐客网

  1. 首页 > it技术 > >

（ssl 2293）暗黑游戏#二维费用背包#


Description
暗黑游戏中，装备直接决定玩家人物的能力。可以使用Pg和Rune购买需要的物品。暗黑市场中的装备，每件有不同的价格（Pg和Rune）、能力值、最大可购买件数。Kid作为暗黑战网的一个玩家，当然希望使用尽可能少的Pg和Rune购买更优的装备，以获得最高的能力值。请你帮忙计算出现有支付能力下的最大可以获得的能力值。
分析：Pg和Rune说明要支付两种费用（二维费用背包）。

  • #include using namespace std; int n,sp,sr,p[151],r[151],s[151],m[151],f[101][101]; int main(){ scanf("%d%d%d",&n,&sp,&sr); for (int i=1; i<=n; i++) scanf("%d%d%d%d",&p[i],&r[i],&s[i],&m[i]); for (int i=1; i<=n; i++)

  • if (s[i]) //多重背包

  • for (int y=1; y<=s[i]; y++) //数量 for (int j=sp; j>=0; j--)//01背包 for (int k=sr; k>=0; k--){//01背包 int t1=j+p[i]; int t2=k+r[i]; if (t1>sp) continue; //不够钱重新枚举 if (t2>sr) continue; //the same if (f[t1][t2]sp) continue; //the same if (t2>sr) continue; // the same if (f[t1][t2]



【（ssl 2293）暗黑游戏#二维费用背包#】

    推荐阅读


    上一篇：通用nodejs开发架构

    下一篇：设计模式 —— 组合模式