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说明刚好用完)

注意: