程序员人生网站导航

POJ 3260 The Fewest Coins(多重背包+完全背包)

栏目：互联网时间：2014-11-21 08:18:57

http://poj.org/problem?id=3260

题意:

John要去买价值为m的商品. 现在的货币系统有n种货币,对应面值为val[1],val[2]…val[n]. 然后他身上每种货币有num[i]个. John必须付给售货员>=m的金钱, 然后售货员会用最少的货币数量找钱给John.

问你John的交易进程中, 他给售货员的货币数目+售货员找钱给他的货币数目的和最小值是多少?

分析:

本题与POJ 1252类型:

http://blog.csdn.net/u013480600/article/details/40454963

假定John付款总额为S时的货币数目为T1, 售货员找钱 (S-m) 的货币数目为T2. 我们要使得T1+T2最小, 那末自然T1和T2也必须各自是最小的(即T1是当John付款正好S时,最少需要多少张货币. T2是当售货员正好找钱S-m时,最少需要多少张货币.).

John给的钱肯定>=m, 但是到底最大多大呢? 如果我们直接求John的所有金钱总和, 然后再DP, 肯定超时. 这个up_bound (即john最多给售货员的钱数) 可以简单设置1个大数值便可. 网上有个证明(这个证明我也有点不明白):

John的付款数最多为maxv*maxv+m

证明以下：

如果John的付款数大于了maxv*maxv+m，即付硬币的数目大于了maxv，根据鸽笼原理，最少有两个的和对maxv取模的值相等(这个意思应当是:最少maxv+1个硬币对maxv求余,然后余数属于[0,maxv⑴]范围,肯定有最少两个硬币的余数相同的)，也就是说，这部份硬币能够用更少的maxv来代替(这句话我不理解)。证毕。

第1个问题是1个多重背包问题.

令dp[i][j]==x 表示当John用前i种货币组成j元钱时, 最少需要x张货币.

初始化: dp全为INF(无穷大), 且dp[0][0]=0.

对每种货币, 我们分情况对它进行处理:

1. 如果val[i]*num[i]>=up_bound时, 做1次完全背包.

2. 如果val[i]*num[i]<up_bound时, 做屡次01背包.

终究所求: dp[n][i] 其中i属于[m, up_bound].

第2个问题是1个完全背包问题.

令dp2[i][j]==x 表示售货员用前i种硬币组成j元钱时, 最少需要x张货币.

初始化: dp2全为INF(无穷大), 且dp2[0][0]=0.

状态转移: dp2[i][j] = max( dp2[i⑴][j] , dp2[i][j-val[i]]+1 )

终究所求: dp2[n][i] 其中i属于[m, up_bound].

终究合并问题1和问题2的解, 我们枚举i从m到up_bound, 找出dp[i]+dp2[i-m]的最小值便可.

AC代码:

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define INF 1e9 int n;//n种硬币 int m;//购买商品的价值 int up_bound;//DP价值上界 int val[100+5];//每种硬币价值 int num[100+5];//每种硬币数目 int dp[55555]; //多重背包 int dp2[55555];//完全背包 //1次01背包 void ZERO_ONE_PACK(int *dp,int cost,int sum) { for(int i=up_bound;i>=cost;i--) dp[i] = min(dp[i], dp[i-cost]+sum);//注意这里是+sum } //1次完全背包 void COMPLETE_PACK(int *dp,int cost) { for(int i=cost;i<=up_bound;i++) dp[i] = min(dp[i], dp[i-cost]+1); } //1次多重背包 void MULTIPLY_PACK(int *dp,int cost,int sum) { if(cost*sum>=up_bound) { COMPLETE_PACK(dp,cost); return ; } int k=1; while(k<sum) { ZERO_ONE_PACK(dp,cost*k,k); sum -=k; k *=2; } ZERO_ONE_PACK(dp,cost*sum,sum); } int main() { while(scanf("%d%d",&n,&m)==2) { //读取输入+计算上界 int max_val=0; for(int i=1;i<=n;i++) { scanf("%d",&val[i]); max_val= max(max_val,val[i]); } for(int i=1;i<=n;i++) scanf("%d",&num[i]); up_bound=max_val*max_val+m;//上界 //初始化dp和dp2 for(int i=1;i<=up_bound;i++) dp[i]=dp2[i]=INF; dp[0]=dp2[0]=0; //递推进程 for(int i=1;i<=n;i++) { MULTIPLY_PACK(dp,val[i],num[i]); COMPLETE_PACK(dp2,val[i]); } //统计结果 int ans=INF; for(int i=m;i<=up_bound;i++) ans= min(ans, dp[i]+dp2[i-m]); printf("%d ",ans==INF?⑴:ans); } return 0; }

------分隔线----------------------------

上一篇 沟通和编程一样，也是一门艺术系列5（沟通的方向）

下一篇 PL/SQL Developer中调试oracle的存储过程

------分隔线----------------------------