hdu 1284 钱币兑换问题 完全背包求指定容量方案数

缘起

【1】中研究了01背包最优解决方案的个数. 本文研究一下01背包、完全背包装满背包条件下的方案数.

hdu 1284 钱币兑换问题

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

Input
每行只有一个正整数N，N小于32768。

Output
对应每个输入，输出兑换方法数。

Sample Input
2934
12553

Sample Output
718831
13137761

限制
1s

首先关于这种问题常见于面试题

1
2
3
4
5
6
7
8
9
网上各大公司经常出题目：假设现在有1元、2元、5元的纸币很多张，现在需要20块钱，你能给多少种找
钱方案，这就可以认为是完全背包装满背包求方案数的问题，即背包容量为20，物品体积分别为1、2、5。
所以再换个角度看不定方程的非负整数解的个数不也就是这个问题吗?

还有公司出题目：给定一个数m，将m拆成不同的自然数的和的形式有多少种方案，这就是典型的01背包
问题，背包容量为n，物品件数为k，这里面的k是隐含条件，可以求出来，因为n最多由1+2+…+k得到，由此
可以根据n求得物品件数的上限k。而【3】就是对n使用1,..,k进行完全背包得到方法数（去看看【3】,是不是那里的
dp方程和这里很像呢（逃~）?）. 
而如果面试要求不同的整数的话, 就是对n进行1,...,k的01背包方案数.

本文汲取了【2】这篇好文的思想.

01背包求装满背包的方案数

问题的定义
1
2
设背包容量为V，一共N件物品，每件物品体积为C[i]，每件物品的价值为W[i]，每件物品至多选择一次
求将背包装满的方案总数。
问题的求解

dp. 令F[i][j] 是前i件物品,j的容量限制的背包, 恰好将背包装满的方案数. 则根据选与不选第i件物品. 我们得到如下dp方程

初始化条件是 F[0][0] =1, 其余都是0. 即不选任何物品的话, 背包容量只有为0, 才有一种方案将背包装满, 否则都是没办法的.

显然对i进行滚动优化掉. 得到了O(NV)时间复杂度、O(V) 空间复杂度的算法, 伪代码如下

1
2
3
4
5
6
memset(F,0)
F[0] = 1;
for i = 1,...,N
	for j = V,...,C[i]  // 倒序才能保证每件物品至多选取一次
		F[j] += F[j-C[i]]
return F[v]

完全背包求装满背包的方案数

问题的定义
1
2
设背包容量为V，一共N件物品，每件物品体积为C[i]，每件物品的价值为W[i]，每件物品可选取无限次.
求将背包装满的方案总数。
问题的求解

dp. 令F[i][j] 是前i件物品,j的容量限制的背包, 恰好将背包装满的方案数. 则根据选与不选第i件物品. 我们得到如下dp方程

初始化条件是 F[0][0] =1, 其余都是0. 即不选任何物品的话, 背包容量只有为0, 才有一种方案将背包装满, 否则都是没办法的.

显然对i进行滚动优化掉. 得到了O(NV)时间复杂度、O(V) 空间复杂度的算法, 伪代码如下

1
2
3
4
5
6
memset(F,0)
F[0] = 1;
for i = 1,...,N
	for j = C[i],...,V  // 正序才能保证每件物品随意选
		F[j] += F[j-C[i]]
return F[v]

其实如果01和完全背包会的了话,则对于多重背包求方法数和多重背包转01背包+完全背包是一样的. 基本思路就是拆成单件物品

回到本题, 本题显然属于完全背包恰好装满背包的方案总数计算问题. 有了上面的讲解. 则不难写下本题的ac代码

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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL
const int maxv = 33000;
int n, dp[maxv];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d", &n))
	{
		memset(dp,0,sizeof(dp));
		dp[0] = 1;
		for (int i = 1;i<=3;i++)
		{
			for (int v = i;v<=n;v++)
			{
				dp[v]+=dp[v-i];
			}
		}
		printf("%d\n", dp[n]);
	}
	return 0;
}

ac情况

Status Accepted
Time 124ms
Memory 1864kB
Length 429
Lang C++
Submitted 2019-10-27 11:11:39
Shared
RemoteRunId 31128590

参考

【1】https://yfsyfs.github.io/2019/10/27/hdu-2126-Buy-the-souvenirs-01%E8%83%8C%E5%8C%85%E6%B1%82%E6%9C%80%E4%BC%98%E6%96%B9%E6%A1%88%E6%95%B0/

【2】https://blog.csdn.net/wumuzi520/article/details/7021210

【3】https://yfsyfs.github.io/2019/08/27/poj-3181-Dollar-Dayz-%E9%AB%98%E7%B2%BE%E5%BA%A6-dp/