http://acm.pku.edu.cn/JudgeOnline/problem?id=1276题目大意是:
给定N种面值分别为d[k]的钞票,数量分别为n[k]张.再给一个整数cash.
求,用这些钞票能表示出的不大于cash的最大值是多少.
数据范围N<=1000, n[k]<=1000, cash<=100000
最简单的DP思路是大背包.把每一张钞票看成一件物品,把cash看成背包容量.
这样的复杂度是O(sigma(n[k])*cash),上限是10^11,显然难以应付1000ms的时限.
此处便需利用一个整数的性质来压缩钞票数:
易知,1,2,4,...,2^(k-1)这些数的线性组合,可以表示出任意小于2^k的正整数.
所以如果n[i]=2^k-1,那么实际上钞票k,就可以转化为分别用系数(1,2,4,...,2^k-1)去乘d[k]而得到的钞票各一张.
如果n[i]!=2^k-1,只需取系数1,2,4,..,2^(k-1),n[i]-(2^k-1),其中k是使2^k-1<=n[i]的最大整数.
代码如下:
1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4 int dp[100010],mark;
5 int sn,cash;
6 struct BILL{
7 int n,d;
8 }b[1010];
9 int ans;
10
11 void go_dp(){
12 int i,k,upb,r,s;
13 dp[0]=mark;
14 ans=0;
15 for(k=0; k<sn; k++){
16 r=1; //系数:2的幂次
17 while(b[k].n>0){
18 if((r<<1)-1>b[k].n){
19 r=b[k].n-(r-1);
20 b[k].n=0;
21 }
22 s=r*b[k].d; //新钞票的面值
23 upb=min(ans+s,cash);
24 for(i=upb; i>=s; i--){
25 if(dp[i-s]==mark){
26 dp[i]=mark;
27 if(ans<i) ans=i;
28 }
29 }
30 r<<=1;
31 if(ans==cash) return;
32 }
33 }
34 }
35
36 int main(){
37 int i,j,k;
38 mark=0;
39 while(scanf("%d%d",&cash,&sn)!=EOF){
40 ans=0; mark++;
41 for(i=0;i<sn;i++){
42 scanf("%d%d",&b[i].n,&b[i].d);
43 ans+=b[i].n*b[i].d;
44 }
45 if(ans>cash)
46 go_dp();
47
48 printf("%d\n",ans);
49 }
50 return 0;
51 }
52
另,在网上搜得另一种思路,开bool数组记录每个总额是否能达到,开个2维数组记录达到相应总额每种钞票使用数
个人以为,这种方法不能保证总得到最优解.考察如下的例子:
cash=3*4*5=60
钞票(面值*张数):3*19,4*14,5*11
假设55的方案恰好是5*11,56的方案恰好是4*14,57的方案恰好是3*19,那么在考虑60时就找不到解了.实际上60是可以达到的.
posted on 2009-04-11 13:21
wolf5x 阅读(408)
评论(0) 编辑 收藏 引用 所属分类:
acm_icpc