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 閱讀(425)
評論(0) 編輯 收藏 引用 所屬分類:
acm_icpc