完全背包最优解方案数

缘起

【1】中研究了 01背包最优解方案的个数. 本文研究 完全背包最优解方案的个数。 妈的, 在网上找了半天的题目都没找到.~ 只能干说了~ 本文借鉴了【2】

分析

完全背包问题的定义参见【3】. 本文论述如何求完全背包最优解方案数.

【1】中采用的思路是在处理01背包的时候维护一下计数就好了. 这里其实采用的做法和【1】中类似. 

1
2
3
令 dp[i][j]是只考虑前i件物品的时候, 容量为j的时候,最大背包价值. 
dpp[i][j]是只考虑前i件物品的时候, 容量为j的时候, 实现dp[i][j]的方法数.
则 dp[0][j] 都是0,而dpp[0][j] = 1, 0<=j<=V

伪代码如下（其实就是在求解完全背包的过程中做点儿事情~）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
memset(dp,0);
fill(dpp,1);
for i = 1,...,N
{
	for j = c[i],...,V
	{
	
		if(dp[j]<dp[j-c[i]]+w[i])
		{
			dp[j] = dp[j-c[i]]+w[i];
			dpp[j] = dpp[j-c[i]];
		}
		else
		{
			dpp[j] += dpp[j-c[i]];		
		}
	}
}
return dpp[V];

参考

【1】https://yfsyfs.github.io/2019/10/27/hdu-2126-Buy-the-souvenirs-01背包求最优方案数/

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

【3】https://yfsyfs.github.io/2019/08/19/poj-1384-Piggy-Bank-%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85/