HDU 2844 Coins (多重背包计数 空间换时间) - Tc_To_Top的专栏 - 博客频道 - CSDN.NET

HDU 2844 Coins (多重背包计数 空间换时间) - Tc_To_Top的专栏 - 博客频道 - CSDN.NET

Whuacmers use coins.They have coins of value A1,A2,A3...An Silverland dollar. One day Hibix opened purse and found there were some coins. He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn't know the exact price of the watch.

You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins.

Input

The input contains several test cases. The first line of each test case contains two integers n(1 ≤ n ≤ 100),m(m ≤ 100000).The second line contains 2n integers, denoting A1,A2,A3...An,C1,C2,C3...Cn (1 ≤ Ai ≤ 100000,1 ≤ Ci ≤ 1000). The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0 

Sample Output

8  4

题目大意：n种数，每个数的值为ai,有ci个，求能组成多少个不大于m的不同的数字

1.     while(scanf("%d %d", &n, &m) != EOF && (n + m))  
2.     {  
3.         memset(dp, false, sizeof(dp));  
4.         for(int i = 1; i <= n; i ++)  
5.             scanf("%d", &a[i]);  
6.         for(int i = 1; i <= n; i ++)  
7.             scanf("%d", &c[i]);  
8.         dp[0] = true;  
9.         int ans = 0;  
10.         for(int i = 1; i <= n; i ++)  
11.         {  
12.             memset(cnt, 0, sizeof(cnt));  
13.             for(int s = a[i]; s <= m; s ++)  
14.             {  
15.                 if(!dp[s] && dp[s - a[i]] && cnt[s - a[i]] < c[i])  
16.                 {  
17.                     dp[s] = true;  
18.                     ans ++;  
19.                     cnt[s] = cnt[s - a[i]] + 1;  
20.                 }  
21.             }  
22.         }  
23.         printf("%d\n", ans);  
24.     }  

1.     while(scanf("%d %d", &n, &m) != EOF && (n + m))  
2.     {  
3.         memset(dp, false, sizeof(dp));  
4.         for(int i = 1; i <= n; i ++)  
5.             scanf("%d", &a[i]);  
6.         for(int i = 1; i <= n; i ++)  
7.             scanf("%d", &c[i]);  
8.         dp[0] = true;  
9.         int ans = 0;  
10.         for(int i = 1; i <= n; i ++)  
11.         {  
12.             memset(cnt, 0, sizeof(cnt));  
13.             for(int s = a[i]; s <= m; s ++)  
14.             {  
15.                 if(!dp[s] && dp[s - a[i]] && cnt[s - a[i]] < c[i])  
16.                 {  
17.                     dp[s] = true;  
18.                     ans ++;  
19.                     cnt[s] = cnt[s - a[i]] + 1;  
20.                 }  
21.             }  
22.         }  
23.         printf("%d\n", ans);  
24.     }  

http://blog.sina.com.cn/s/blog_626631420100u9tf.html

IF 价值×数量>=m

       THEN 取这个硬币的次数相当于无限制，可以考虑成完全背包

ELSE

       THEN 考虑成0-1背包（二进制优化），就是把这个硬币的v和num组合出0-1背包可能出现的状态（可以去看背包九讲）

（对于num，类似于编码。  当2^n <=num/2时：k = 2^n（n=0，1，2，……）表示状态，对应下来就是二进制的某一位数是1，然后还有一个状态就是k>num/2的时候啦，num+1-k，这样下来就可以用k来组合枚举出从1->num的所有可能了。然后对于k，单位价值和大小都乘上k之后就变成了一个0-1背包）

http://www.cnblogs.com/AC-Phoenix/p/4485923.html
http://code.qtuba.com/article-55843.html

void MultipleSack(int v,int num)

{

    int i,j,k;

    int space;

    if (v*num >= m)

    {

        //用完全背包去求

        for (space = v; space <= m; space++)

        {

            knap[space] = knap[space]|knap[space-v];

        }

    }

    //用0-1背包去求，二进制优化

    for (k = 1; k<=num/2; k=(k<<1))

    {

        for (space = m; space >= k*v; space--)

            knap[space] = knap[space]|knap[space-k*v];

    }

    k = num+1-k;

    for (space = m; space >= k*v; space--)

        knap[space] = knap[space]|knap[space-k*v];

    return ;

}

int main()

{

    freopen("Sample Input.txt","r",stdin);

    int i,j,k,t;

    while (scanf("%d%d",&n,&m),n&&m)

    {

        for (i = 1; i <= n; i++)

            scanf("%d",&v[i]);

        for (i = 1; i <= n; i++)

            scanf("%d",&num[i]);

        memset(knap,0,sizeof(knap));

        knap[0] = 1;

        for (i = 1; i <= n; i++)

            MultipleSack(v[i],num[i]);

        for (i = 1,t = 0; i <= m; i++)

            t += knap[i];

        printf("%d\n",t);

    }

    getch();

    return 0;

}

Read full article from HDU 2844 Coins (多重背包计数 空间换时间) - Tc_To_Top的专栏 - 博客频道 - CSDN.NET