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

新睿云服务器60天免费使用,快来体验!>>>   

/*
http://acm.hdu.edu.cn/showproblem.php?pid=1114
完全背包问题 再判断背包能否装满

题意:
给出存空钱罐的重量以及装满时的重量
给出每种硬币的面值以及重量
求 存钱罐装满时的最小价值。。。若不能装满输出This is impossible

值得注意的两点的是
(1) dp数组的初始化
因为要求的是最小值 所以dp数组赋为最大值但是dp[0]的值为0;
(2) 如何判断背包是否装满

物品个数n
背包容量 C
for(int i=1;i<=n;i++)
for(int j=weight[i];j<=C;j++)
dp[j]=min(dp[j],dp[j-weight[i]+value[i]);
当j=C时 如果dp[j-weight[i]]不是初始值 即:
第i个物品和其他的物品组合能把背包装满
如果dp[j-weight[i]]是初始值 即:反之

*/

include

include

include

using namespace std;
const int inf=0x3f3f3f3f;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int E,F;
scanf("%d%d",&E,&F);
int N;
scanf("%d",&N);
int P[505],M[505],dp[10005];
memset(dp,inf,sizeof(dp));
// for(int i=0;i<=F-E;i++)
// dp[i]=inf;
dp[0]=0;
for(int i=1; i<=N; i++)
scanf("%d%d",&P[i],&M[i]);
for(int i=1; i<=N; i++)
for(int j=M[i]; j<=F-E; j++)
dp[j]=min(dp[j],dp[j-M[i]]+P[i]);
if(dp[F-E]==inf)
printf("This is impossible.\n");
else
printf("The minimum amount of money in the piggy-bank is %d.\n",dp[F-E]);
}
return 0;
}

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