FATE(完全背包)
FATE(完全背包)
1944864971 发表于2年前
FATE(完全背包)
  • 发表于 2年前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】买域名送云解析+SSL证书+建站!>>>   

/*
http://acm.hdu.edu.cn/showproblem.php?pid=2159
分析:
和普通的完全背包没有什么太大的区别 但是题目中给出了限制最多可杀s个怪
用二维数组dp[i][j] 表示在所用j忍耐度下杀了 i个人是获得最大的经验值

然后遍历这些经验值 大于最大升级所需经验即可,但是还要找出剩余的最大忍耐度
*/

include

include

include

include

using namespace std;
int main()
{
int v[105],w[105],dp[105][105];
int n,m,k,s;
while(~scanf("%d%d%d%d",&n,&m,&k,&s))
{ memset(dp,0,sizeof(dp));
for(int i=1; i<=k; i++)
scanf("%d%d",&v[i],&w[i]);
for(int i=1; i<=k; i++)
for(int q=1; q<=s; q++)
for(int j=w[i]; j<=m; j++)
dp[q][j]=max(dp[q][j],dp[q-1][j-w[i]]+v[i]);
int maxRenNai=0x3f3f3f3f;
for(int i=0; i<=s; i++)
for(int j=0; j<=m; j++)
if(dp[i][j]>=n)
maxRenNai=min(maxRenNai,j);
if(maxRenNai!=0x3f3f3f3f)
printf("%d\n",m-maxRenNai);//剩下的最大忍耐度
else
printf("-1\n");

}
return 0;

}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: