AcWing 281. 硬币

原題連結

考察:多重背包dp

實際上是考察多重部分和的問題.

在本題如果直接用二進制優化時間複雜度是108  會TLE.是以必須優化

多重背包問題中f[j] = 1是因為上一輪f[j] = 1或者本輪f[j-v] = 1.如果f[j]在枚舉第i-1種硬币時就已經為1,那麼f[j]在第i輪就沒必要在指派.

 這裡有兩種不同的思路但本質是相同的:

lyd大佬的思路:

        需要用一個數組記錄f[j]在階段i時至少需要幾枚硬币.會有幾種情況

1. f[j]在第i-1輪已經為1,那麼不需要指派直接跳過
2. f[j-v]在第i輪為1.那麼我們需要判斷此時再拿一個v會不會超出給定數目,如果超出就跳過.

因為used數組是用來記錄階段i,f[j] = 1要幾枚硬币,used數組也起到限制範圍的作用,同時避免了三層循環.(我覺得使用used數組就行了...)

1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 const int N = 110,M = 100010;
 8 int a[N],c[N];
 9 int f[M],used[M];
10 int main()
11 {
12     int n,m;
13     while(scanf("%d%d",&n,&m)&&(n+m))
14     {
15         memset(f,0,sizeof f); int ans = 0;
16         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
17         for(int i=1;i<=n;i++) scanf("%d",&c[i]);
18         f[0] = 1;
19         for(int i=1;i<=n;i++)
20         {
21             memset(used,0,sizeof used);
22             for(int j=a[i];j<=m;j++)
23               if(!f[j]&&f[j-a[i]]&&used[j-a[i]]+1<=c[i]) f[j] = 1,used[j] = used[j-a[i]]+1;
24         }
25             
26         for(int i=1;i<=m;i++) if(f[i]) ans++;
27         printf("%d\n",ans);
28     }
29     return 0;
30 }      

lyd的思路

白書的思路:

        其實别無二緻.差別就是白書的f[i][j]數組是記錄第i種硬币下,湊成f[j]還剩下多少貨币.(但是實測POJ 2000MS,lyd的方法1297ms)

1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 const int N = 110,M = 100010;
 8 int a[N],c[N],v[N*10];
 9 int f[M];
10 int main()
11 {
12     int n,m;
13     while(scanf("%d%d",&n,&m)&&(n+m))
14     {
15         memset(f,-1,sizeof f); int ans = 0;
16         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
17         for(int i=1;i<=n;i++) scanf("%d",&c[i]);
18         f[0] = 0;
19         for(int i=1;i<=n;i++)
20             for(int j=0;j<=m;j++)
21             {
22                 if(f[j]>=0) f[j] = c[i];
23                 else{
24                     if(j<a[i]||f[j-a[i]]<=0) f[j] = -1;
25                     else if(j>=a[i]&&f[j-a[i]]>0) f[j] = f[j-a[i]]-1;
26                 }
27             }
28         for(int i=1;i<=m;i++) if(f[i]>=0) ans++;
29         printf("%d\n",ans);
30     }
31     return 0;
32 }      

白書

關于白書代碼又有幾個問題:

1.二層循環能不能從a[i]開始.

           答案是不能,二層循環是有兩個分支點:

1. 如果f[j]>=0.這代表上一輪就已經湊成j.
2. f[j]<0此時我們需要從前面f[j-v]判斷f[j-v]剩餘的貨币數還能不能給f[j].

如果從a[i]開始,我們的f[i][0]是沒有初始化為c[i]的.那麼就不能得到貨币.如果每次循環給f[i][0]指派,那和直接放在初始條件有什麼差別

判别答案隻需要判斷目前湊成j錢的時候剩餘錢數是不是>=0(=0說明剛好用完)

注意: