USACO-2.3.4-MoneySystems-背包

(记忆化搜索完全背包多重背包)求方案数。

题意： 题目描述

母牛们不但创建了它们自己的政府而且选择了建立了自己的货币系统。由于它们特殊的思考方式，它们对货币的数值感到好奇。传统地，一个货币系统是由$1,5,10,20$或$25,50,$和$100$的单位面值组成的。母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。举例来说, 使用一个货币系统 ${1,2,5,10,...}$产生$18$单位面值的一些可能的方法是: $ 18x1, 9x2, 8x2+2x1, 3x5+2+1$ ,等等其它。写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。保证总数将会适合long long (C/C++) 和 Int64 (Free Pascal)，即在$0$到$2^{63}-1$之间。 输入输出格式 输入格式： 货币系统中货币的种类数目是 V ($ 1 V 25 $)。要构造的数量钱是 N ($1 \leq N \leq10,000$)。第一行: 二个整数，V 和 N 。第二行：可用的货币的面值。 输出格式: 单独的一行包含那个可能的用这v种硬币凑足n单位货币的方案数。 输入输出样例 输入样例#1： 3 10 1 2 5 输出样例#1： 10 说明翻译来自NOCOW USACO 2.3

做法：

一开始考虑dfs。本来考虑的是用dfs(i)表示，当前还剩下n块钱没有组成。用下面这种方法去解决。

for( int i = 1 ; i <= v ; i++)
	if( n  >= a[i] ) 
		dfs( n - a[i] ) ;
// 退出条件是 n == 0

不过这种方法，后来发现有点蠢。因为我无法处理比如：先选$1$后选$2$ 和先选$2$后选$1$这样的重复情况。想了一下如何去重，发现去重的话，不同情况下不一样。应该是自己走远了。

之后又感觉有点像多重背包。不过自己胡乱操作了一番，用USACO-2-2-2-subset-01背包求方案数曾经自己总结过的，感觉不错的方法来做多重背包，发现遇到了很多问题。因为曾经的方法的不足，感觉有很多变量很多余，或者不知道用来存什么记录什么，比如dp和cnt数组就不知道存什么。曾经的不足即：只是求方案的话，完全没必要去开dp数组，只要一个cnt其实就可以了。我现在回过头来看，感觉dp数组里存的东西很奇怪，完全没必要啊。dp[i][j]难道表示的是前$i$个物品装到容量为$j$的背包里，最大价值吗？感觉完全没必要了。。

这也暴露了自己的一个问题： 1. 对于问题要勤思考，不能生搬硬套。否则就会发现很多东西很模糊不确定，又因为是曾经总结过的，所以又不太敢随意修改。这有点像郑人买履了。以后要尽可能的去思考，有自己的想法，并且敢于去修改和质疑模板的问题。 2. 就算曾经总结过的东西，以后也要反复总结、提炼，不能满足于以前总结的。因为即使曾经总结过的东西，过一段时间提高后再回头看，发现依然有很多不足和问题。所以要不断总结，哪怕之前总结过。

说的有点跑题了。

后来发现那种dfs行不通以后，我考虑用dfs(n,i)表示，当前还剩下$n$个钱没有被表示，目前是第$i$枚硬币。这样写下来的代码为：

code

 
long long dfs( int n , int i )
{
    if( dp[n][i] != - 1 )
        return dp[n][i] ; 
    if( n == 0 )
        return dp[n][i] = 1  ;
    if( i > v )
        return dp[n][i] = 0  ; 
    long long  ans = 0;
    // 枚举对于当前第i枚硬币，可以用 0 ..到 j * a[i]枚。
    for( int j = 0 ; j * a[i] <= n ; j++) 
    {
        ans += dfs( n - j * a[i] , i + 1 ) ; 
    }

    return dp[n][i] = ans ; 
}

成功AC。看到这个dfs后，感觉就是多重背包的意思啊。所以又进一步想了下如何改成多重背包。对于多重背包来讲，用dp[i][j]表示对于i个物品，放在容积为j的背包里的方案数(这里之前的博客里就是有点问题，表达的太啰嗦了)。那么边界条件就是dp[0][0] = 1 , dp[others][others] = 0 显然只有$0$个物品，放在$0$的背包里的方案数是$1$，除此之外其他都是$0$。转移的话，只是再加一个维度，考虑对于当前的物品可以考虑放$0$到$ j * a[i] n$个情况。转移即可。

dp[0][0] = 1 ;
for( int i = 1 ; i <= v ; i++)
{
	for( int j = 0 ; j <= n ; j++)
	{
		for( int k = 0 ; k * a[i] <= j ; k++)
		{
			dp[i][j] += dp[i-1][j-k*a[i]] ;
		}
	}
}

PS：多重背包正常是有优化的，可以用二进制拆分后看做是01背包。

之后，对背包学艺不精的我突然发现，这其实是完全背包！多重背包是对于物品使用次数是有限制的，这个没有限制，所以应该是完全背包。完全背包的话，正常的滚动数组的写法其实就是和01背包顺序相反而已。因为对于01背包来说，决策的状态必须对于每个物品放或者不放决策一次，不能重复。而完全背包因为物品可以随便选，决策过的可以再决策再选择一次，所以可以从曾计算过的状态再决策得来。因为初学，所以这些都还没有使用滚动数组。不过这也导致自己在写完全背包的时候遇到了一点困难。网上的都是滚动数组优化过的，当我想写一个不优化的方便理解的时候，发现找不到代码。

dp[0][0] = 1 ;
for( int i = 1 ; i <= v ; i++)
{
	for( int j = 0; j <= n ; j++)
	{
		if( j >= a[i] ) 
			dp[i][j] = dp[i-1][j] + dp[i][ j - a[i] ] ;
		else 
			dp[i][j] = dp[i-1][j] ;
	}
}

这个一开始遇到的坑是，模仿别人的滚动数组的j = a[i] .. n ，然后答案总是差一点。后来发现问题是因为对于$ j < a[i]$的时候，状态应该移动过来。不然的话计算出来的状态其实是有缺失的。滚动数组的写法省了这个问题，所以自己一直没注意到。

这个主要的决策问题就是dp[i][j] = dp[i-1][j] + dp[i][ j - a[i] ]; 。对于01背包来说，只有选或者不选两种。应该都是从上一个物品的情况转移而来，这样对于当前物品来说，只会有不选当前物品，从dp[i-1][j]转移，和选了当前物品，从dp[i-1][j-a[i]]转移，这两种情况都是没有选当前物品的，转移过来的话，也只会是没选和选。不过出现选择多个的情况。但是因为对于完全背包来说，已经选择过的物品可以再次选择，所以我们应该是从之前已经决策过拿还是没拿的物品转移而来。对于dp[i][j-a[i]]这个状态来说，可能之前已经拿过第i个物品，也可能没拿过，但是who cares? 因为我物品是没有限制的，所以只要直接这么决策过来就可以了。

对于目前的这些知识，自己还只是雏形，理解不是很透彻。在这个阶段本文是对自己的思路进行一下简单整理和总结，便于以后提高。有错误的话十分麻烦各位能花一点点时间指出出来。

最近对DP这类问题，发现自己总是爱用记忆化搜索的方法去写。总是先想搜索，然后才能转成递推。而网上的答案和代码等几乎都是清一色的递推的方法。一开始我以为只是因为递推常数小，所以写熟练了大家都是这样直接写递推的,对于这个问题只是我自己的思维差异，不需要太重视。后来问了一下学长，学长表示：“这个问题还是挺需要注意的，很多时候DP用递推比用记忆化要好写很多。而且递推这种思维方法其实才是DP的本质。也就是先想状态再想转移最后想边界，状态和转移有了的话，很多时候就能写递推了。”学长建议我以后思考尽量用递推，代码会比较少，也比较好调试。而且这种思维方法挺需要注意的。