Coins HDU

多重背包可行性

当做一般多重背包，二进制优化

 1 #include<cstdio>
 2 #include<cstring>
 3 int n,m,anss;
 4 int a[110],c[110],f[100100];
 5 int main()
 6 {
 7     int i,j,t;
 8     scanf("%d%d",&n,&m);
 9     while(n!=0||m!=0)
10     {
11         anss=0;
12         memset(f,0,sizeof(f));
13         for(i=1;i<=n;i++)
14             scanf("%d",&a[i]);
15         for(i=1;i<=n;i++)
16             scanf("%d",&c[i]);
17         f[0]=1;
18         for(i=1;i<=n;i++)
19         {
20             t=1;
21             while(c[i]>0)
22             {
23                 if(t>c[i])    t=c[i];
24                 c[i]=c[i]-t;
25                 for(j=m;j>=a[i]*t;j--)
26                     f[j]|=f[j-a[i]*t];
27                 t*=2;
28             }
29         }
30         for(i=1;i<=m;i++)
31             if(f[i])
32                 anss++;
33         printf("%d
",anss);
34         scanf("%d%d",&n,&m);
35     }
36     return 0;
37 }

二进制优化+bitset压位

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<bitset>
 4 using namespace std;
 5 int n,m,anss;
 6 int a[110],c[110];
 7 bitset<100100> f;
 8 int main()
 9 {
10     int i,j,t;
11     scanf("%d%d",&n,&m);
12     while(n!=0||m!=0)
13     {
14         anss=0;
15         f.reset();
16         for(i=1;i<=n;i++)
17             scanf("%d",&a[i]);
18         for(i=1;i<=n;i++)
19             scanf("%d",&c[i]);
20         f[0]=1;
21         for(i=1;i<=n;i++)
22         {
23             t=1;
24             while(c[i]>0)
25             {
26                 if(t>c[i])    t=c[i];
27                 c[i]=c[i]-t;
28                 f|=(f<<(a[i]*t));
29                 t*=2;
30             }
31         }
32         for(i=1;i<=m;i++)
33             if(f[i])
34                 anss++;
35         printf("%d
",anss);
36         scanf("%d%d",&n,&m);
37     }
38     return 0;
39 }

可以转换成完全背包

http://blog.csdn.net/ac_hell/article/details/51394432

（仅做记录）④对于朴素的方法，这个算法每次只记录一个bool值，损失了不少信息。在这个问题中，不光能够求出是否能得到某个金额，同时还能把得出了此金额时A_i还剩下多少个算出来，这样直接省掉了k那重循环。

我们优化dp的状态：

状态：dp[i][j] : = 用前i种硬币凑成j时第i种硬币最多能剩余多少个（ - 1表示配不出来）

转移：

①若dp[i-1][j]>=0，即前i-1种可以配成j，所以根本用不到第i种，所以剩余C_i种 dp[i][j]=C_i

②若j<a[i] || dp[i][j-a[i]]<=0，由于dp[i-1][j]<0，所以要想配成j起码得要有第i种，若j<a[i]则第i种用不到，所以前i种仍配不到j，若dp[i][j-a[i]]<=0，则说明配成j-a[i]时第i种已经无剩余或者甚至无法配成j-a[i]，更别说配成j了， dp[i][j]=-1

③其他情况，由于a[i]还有剩，所以dp[i][j]相当于在dp[i][j-a[i]]的基础上多使用了一个a[i]，此时 dp[i][j]=dp[i][j-a[i]]-1

最终找出所有>=0的dp[n][i]个数就行了（1<=i<=m）

#include<cstdio>
#include<cstring>
#include<bitset>
using namespace std;
int n,m,anss;
int a[110],c[110];
int ans[100100];
int main()
{
    int i,j,t;
    scanf("%d%d",&n,&m);
    while(n!=0||m!=0)
    {
        anss=0;
        memset(ans,-1,sizeof(ans));
        ans[0]=0;
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(i=1;i<=n;i++)
            scanf("%d",&c[i]);
        for(i=1;i<=n;i++)
            for(j=0;j<=m;j++)
                if(ans[j]>=0)
                    ans[j]=c[i];
                else if(j<a[i]||ans[j-a[i]]<=0)
                    ans[j]=-1;
                else ans[j]=ans[j-a[i]]-1;
        for(i=1;i<=m;i++)
            if(ans[i]>=0)
                anss++;
        printf("%d
",anss);
        scanf("%d%d",&n,&m);
    }
    return 0;
}

另：二进制优化+bitset压位比转成完全背包要快，可能常数优越？