ACM刷题之路（二十四）HDU 2844 多重背包转换 Coins

桃扇骨 2024-02-19 20:42 64阅读 0赞

[题目链接：传送门][Link 1]

## **Coins** ##

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 24496 Accepted Submission(s): 8740**

**Problem Description**

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.

#### 题意： ####

**3 10 // N=3 三个硬币 M = 10 所求最大方案价值为10**

**1 2 4 //三个硬币的价值分别为1 、 2 、4**

**2 1 1//三个硬币的数量分别为2 、1 、 1**

**求 能否满足用这三种硬币 凑出价值1 到 10 的方案**

比如1 = 1；2 = 1 + 1；3 = 2 + 1；4 = 4；5 = 4 + 1；6 = 4 + 2；7 = 4 + 2 + 1；8 = 4 + 2 + 1 + 1；

所以1到10可以满足8个币值的方案，输出8.

## 分析： ##

其实这题也看似母函数的模板题，但这周再集训学dp动态规划，所以我用**多重背包**来AC。

我首先想到的思路是**多重背包，转01背包，加一个二进制优化**，就是下列代码所示：

for (int i = 0; i < n; i++) {
                int bei = 1;
                while (a[i].geshu > 0) {
                    if (a[i].geshu & 1) {
                        b[len++] = a[i].jiazhi * bei;
                    }
                    bei *= 2;
                    a[i].geshu /= 2;
                }
            }

后来就一直超时，加了输入挂还是超时，所以试了一种**多重背包转换为二进制01背包+完全背包**的方法。

即：如果你**某个硬币的数量乘以币值，大于等于要求的M**(第一行第二个数)，那么就可以看作是**完全背包**来做题了，套完全背包的模板：（有点断章取义，可以从最后的总代码来看）

if (jia[i] * shu[i] >= m)
    {
    	for (int j = jia[i]; j <= m; j++) 
            {
        	    dp[j] = maxx(dp[j], dp[j - jia[i]] + jia[i]);
    	}
    }

如果**某个硬币的数量乘以币值，不到要求的M**，那么就需要**转化为2进制01背包**了。

代码如下所示：

else 
    {
        for (int k = 1; k  <= shu[i]; k *= 2)
        {
    	for (int j = m; j >= jia[i] * k; j--) 
            {
    		dp[j] = maxx(dp[j], dp[j - jia[i] * k] + jia[i] * k);
    	}
    	shu[i] -= k;
        }
    	if (shu[i] > 0)
            {
    		for (int j = m; j >= shu[i] * jia[i]; j--) 
                    {
    			dp[j] = maxx(dp[j], dp[j - shu[i] * jia[i]] + shu[i] * jia[i]);
    	        }
    	}
    }

**刚开始初始化dp数组为负无穷，且dp\[0\] = 1；**

**如果dp\[i\]可以为正数，那么肯定是从dp\[0\]加硬币加上来的，所以就可以满足刚好凑到i价值的情况。**

#include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int maxx(int x, int y) {
    	return x > y ? x : y;
    }
    int jia[102];
    int shu[102];
    int dp[100010];
    int main()
    {
    	int n, m;
    	while (~scanf_s("%d%d", &n, &m)) {
    		if (n == 0 && m == 0) break;
    		for (int i = 0; i < n; i++) {
    			scanf_s("%d", &jia[i]);
    		}
    		for (int i = 0; i < n; i++) {
    			scanf_s("%d", &shu[i]);
    		}
    		fill(dp, dp + 100010, -999999);
    		dp[0] = 1;
    		for (int i = 0; i < n; i++) {
    			if (jia[i] * shu[i] >= m) {
    				for (int j = jia[i]; j <= m; j++) {
    					dp[j] = maxx(dp[j], dp[j - jia[i]] + jia[i]);
    				}
    			}
    			else {
    				for (int k = 1; k  <= shu[i]; k *= 2) {
    					for (int j = m; j >= jia[i] * k; j--) {
    						dp[j] = maxx(dp[j], dp[j - jia[i] * k] + jia[i] * k);
    					}
    					shu[i] -= k;
    				}
    				if (shu[i] > 0) {
    					for (int j = m; j >= shu[i] * jia[i]; j--) {
    						dp[j] = maxx(dp[j], dp[j - shu[i] * jia[i]] + shu[i] * jia[i]);
    					}
    				}
    			}
    		}
    		int ans = 0;
    		for (int i = 1; i <= m; i++) {
    			if (dp[i]) {
    				ans++;
    			}
    		}
    		printf("%d\n", ans);
    	}
    	return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2844