1. 全栈程序员必看首页

HDU_1114 PiggyBank ( dp | 完全背包问题 )

全栈程序员-站长 • • 未分类 • 阅读 2

HDU_1114 PiggyBank ( dp | 完全背包问题 )文章目录题意题解代码题目连接 hduorvj 题意给 T 组样例 每组第一行空罐的重量 装满的重量每组 n 种物品价值 重量求最小价值题解数量不限 那么完全背包问题板子直接上 不过这个是求的最小价值那么来想一下 求最大价值的时候 dp 数组是全都清零那么求最大值 就需要初始化为 INF 但是这样还漏掉了一点 接着看 来模拟一下 第一件物品

文章目录

题目连接 hdu or vj

题意

求 最小价值

题解

数量不限, 那么完全背包问题板子直接上, 不过这个是求的最小价值

代码

#include  
      using namespace std; #define rg register  #define sc scanf  #define pf printf  typedef long long ll; const int maxn = 5e2+100; const int maxm = 1e5+100; int wei[maxn], val[maxn], dp[maxm]; const int INF = 0x3f3f3f3f; int main ( ) { 
    // freopen( "F:\\in\\.txt" , "r" , stdin );  int T, n, pack_empty, pack_full; sc( "%d", &T ); while ( T-- ) { 
    memset( dp, INF, sizeof(dp) ); dp[0] = 0; // 重量为 0 时价值为 0 sc( "%d%d", &pack_empty, &pack_full ); sc( "%d", &n ); for ( int i = 0; i < n; ++i ) { 
    sc( "%d%d", &val[i], &wei[i]); } int m = pack_full-pack_empty; for( int i = 0; i < n; ++i ){ 
    for( int j = wei[i]; j <= m; ++j ) { 
    dp[j] = min( dp[j] , dp[j-wei[i]]+val[i] ); } } dp[m] != INF ? pf( "The minimum amount of money in the piggy-bank is %d.\n", dp[m] ) : puts( "This is impossible." ); } return 0 ; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/224516.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月17日 上午11:45
下一篇 2026年3月17日 上午11:45


相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号