首页 > 代码库 > poj 1276 Cash Machine(多重背包)
poj 1276 Cash Machine(多重背包)
Cash Machine
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 26954 | Accepted: 9533 |
题目大意:有各种不同面值的货币,每种面值的货币有不同的数量,请找出利用这些货币可以凑成的最接近且小于等于给定的数字cash的金额。
多重背包转0 1背包
对于第 i 种货币可能的状态为w[ i ]到cash
状态方程 dp[j]=dp[ j-c[i] ]+w[i] (c[ i ] 表示”体积“ 实际上就是价值 等于w[ i ]便于区分 )
用count[ i ]来记录n[ i ]中货币的使用次数 注意每次进入内循环之前(也就是更换货币之前都要将count 清0)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int main() { int cash,num,i,j; int n[15]; int w[15]; int dp[10001]; int count[10001]; while(cin>>cash>>num) { for(i=0;i<num;i++) cin>>n[i]>>w[i]; memset(dp,0,sizeof dp); for(i=0;i<num;i++) { memset(count,0,sizeof count); for(j=w[i];j<=cash;j++) if(dp[j]<dp[j-w[i]]+w[i]&&count[j-w[i]]<n[i]) { dp[j]=dp[j-w[i]]+w[i]; count[j]=count[j-w[i]]+1; } } cout<<dp[cash]<<endl; } return 0; }
poj 1276 Cash Machine(多重背包)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。