poj 1742 Coins 多重背包

缘起

虽然本文名称为多重背包，但是使用的方法并不是传统意义上的背包问题的解法，确切讲——我们改变了dp的意义. 至于经典的多重背包问题的dp解法（二进制优化、单调队列优化）以后再写文章

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
给你n种面值的硬币，面值为a1...an，数量分别为c1...cn，求问，在这些硬币的组合下，能够多少种面值，该面
值在[1,m]范围内

【输入】
多样例，每个样例占据2行，第一行是两个正整数n（1<=n<=100）和m（1<=m<=100000）,第二行包含2n个正整数——a1,a2,a3...an,c1,c2,c3...cn (1<=ai<=100000,1<=ci<=1000) 最后的用例以 (0,0)结尾.

【输出】
每个用例输出能够组合成的面值的个数

【样例输入】
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

【样例输出】
8
4

【限制】
Time limit 3000 ms
Memory limit 30000 kB

【source】
楼教主的男人八题之一

令 （对于dp而言，dp的对象的选取直接影响了dp的效率和解题的复杂程度）

1
dp[i][j] = 用前i种币值组成面值j, a[i]最多能剩余多少枚. 1<=i<=n, 0<=j<=m

则
$$
dp[i][j]=\begin{cases}
c[i], \ if\ dp[i-1][j]>=0 \
-1, \ if \ j<a[i] \ || \ dp[i][j-a[i]]\le 0 \
dp[i][j-a[i]]-1, \ else
\end{cases}
$$
上面的式子第一行是不难理解的——如果前面i-1种币值就可以组成面值j的话, 则根本不需要a[i]出手, 所以最多剩余 c[i]枚. 反正，如果前面i-1种币值无法组成j的话，则一定要a[i]出手, 但是如果 j<a[i], 一旦a[i]出手, j也无法实现, 则就是-1（dp[i][j]=-1表示前i种币值无法组成面值j）, 或者 dp[i][j-a[i]]<=0的话, 则表明组成j-a[i]这个面值已经耗尽了a[i], 则根本无法组成面值j的. 则也是-1，其余情况就是前i-1种币值无法组成面值j,并且a[i]<j, 而且前i种币值组成j-a[i]并没有耗尽a[i], 则就是 dp[i][j-a[i]]-1. 所以上述dp方程成立. 而且上述第二个式子意味着内层循环是从小到大的

滚动数组一波得到
$$
0\le j \le m, \ dp[j]=\begin{cases}
c[i], \ if\ dp[j]>=0 \
-1, \ if \ j<a[i] \ || \ dp[j-a[i]]\le 0 \
dp[j-a[i]]-1, \ else
\end{cases}
$$

有了上面的dp方程，解题就很简单了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL

int n,m, a[105],c[105], dp[100005];

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d%d", &n, &m), n||m)
	{
		for (int i = 1; i<=n; i++) scanf("%d", a+i);
		for (int i = 1; i<=n; i++) scanf("%d", c+i);
		memset(dp, -1, sizeof(dp));
		dp[0] = 0; // 不选任何硬币, 要达到0面值 a[0]最多剩余0枚,其余币值都不可达
		for (int i = 1; i<=n; i++)
		{
			for (int j = 0; j<=m; j++) // 注意, 这里要从0开始
			{
				if (dp[j]>=0)
				{
					dp[j] = c[i];
				}
				else if (j<a[i]||dp[j-a[i]]<=0)
				{
					dp[j] = -1;
				}
				else
				{
					dp[j] = dp[j-a[i]]-1;
				}
			}
		}
		int ans = 0;
		for (int i = 1; i<=m;i++)
		{
			if (dp[i]>=0) // 如果使用n个币种组成币值i,a[n]最多剩下的枚数>=0
			{
				ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

ac情况（跑的有点慢~ QAQ）

Status Accepted
Time 2047ms
Memory 480kB
Length 853
Lang C++
Submitted 2019-08-19 22:03:18
Shared
RemoteRunId 20770410