首页 > 代码库 > HDU 1114 完全背包问题的转化
HDU 1114 完全背包问题的转化
题目大意:
根据存钱罐中钱的重量,和每一种钱对应的重量和价值,判断钱能否塞满这个重量,如果能,输出得到的最小价值
这个问题就是要把它和背包问题连接起来,这里钱取得数目是无穷的,所以这里只需要用到完全背包来解决问题
在这里我们定义dp[i][j] 作为重量 j 的条件下,取前 i 中硬币塞满背包可得到的最小价值
1.dp[i][j] = min{dp[i-1][j] , dp[i-1][j-w] + w} 但这里前提是dp[i-1][j-w]和dp[i-1][j]都存在这样的情况
2.如果dp[i-1][j-w]存在dp[i-1][j]不存在,那么dp[i][j] = dp[i-1][j]直接赋值
3.如果均不成立,那么dp[i][j] = 0 表示不存在
然后同样根据背包的思想,二维数组压缩不断滚动更新压缩为一维数组dp[i],表示当前状态在 i 重量下取到的最小值
1 #include <cstdio> 2 #include <cstring> 3 4 using namespace std; 5 const int N = 10005; 6 #define min(a,b) a<b?a:b 7 int dp[N] , M; 8 9 int main()10 {11 int T , E , F , k , w , v;12 scanf("%d" , &T);13 while(T--){14 scanf("%d%d" , &E , &F);15 M = F-E;16 scanf("%d" , &k);17 memset(dp , 0 , sizeof(dp));18 for(int i=0 ; i<k ; i++){19 scanf("%d%d" , &v , &w);20 //用完全背包的形式处理21 for(int i = w ; i<=M ; i++)22 if(dp[i-w] > 0 || i-w == 0){23 if(dp[i] > 0) dp[i] = min(dp[i] , dp[i-w]+v);24 else dp[i] = dp[i-w]+v;25 }26 }27 28 if(dp[M] == 0) puts("This is impossible.");29 else{30 printf("The minimum amount of money in the piggy-bank is %d.\n" , dp[M]);31 }32 }33 }
HDU 1114 完全背包问题的转化
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。