wordpress无法进入后台,搜索引擎优化常用方法,全屋设计师需要学什么,免费搭建网站模板题目描述#xff1a;
给定 V 种货币#xff08;单位#xff1a;元#xff09;#xff0c;每种货币使用的次数不限。
不同种类的货币#xff0c;面值可能是相同的。
现在#xff0c;要你用这 V 种货币凑出 N 元钱#xff0c;请问共有多少种不同的凑法。
输入格式
给定 V 种货币单位元每种货币使用的次数不限。
不同种类的货币面值可能是相同的。
现在要你用这 V 种货币凑出 N 元钱请问共有多少种不同的凑法。
输入格式
第一行包含两个整数 V 和 N。
接下来的若干行将一共输入 V 个整数每个整数表示一种货币的面值。
输出格式
输出一个整数表示所求总方案数。
数据范围
1≤V≤25 1≤N≤10000 答案保证在long long范围内。
输入样例
3 10
1 2 5输出样例
10
分析步骤 第一我们可以看到题目要求我们统计出有多少种凑法每种货币可以用无限次只要不超过N元钱就可以这就非常符合我们的完全背包问题所以我们只需要运用背包DP的方法就可以解出这道题目。 第二运用闫氏DP分析法 根据闫氏DP分析法我们可以知道dp问题可以将其分解为两个步骤第一种是状态表示第二种是状态计算。 我们所有的背包问题都是围绕我们对于集合的定义来的所以这个定义是非常重要的我们将集合定义为所有只从前i个货币中选择总金额不超过 j 的方案的集合。 状态计算由于完全背包是可以无限次的选择物品的所以我们不能和01背包一样只将其分解为选或者不选因为它可以有很多很多种选择可以不选可以选一种可以选两种...只要金额背包体积足够大就可以。 如果他不选择物品 i 那么这种情况相当于从1i - 1中选择金额不超过j的情况是一样的所以我们的表达式是f[i-1][j]。 如果他选择物品 i 那么这样又该如何表示呢我们并不知道他到底要选择几个物品那应该怎么做呢假如我们选择一个的话那么就应该写为f[i-1][j-vi];假如我们选择两个的话那么就应该写为f[i-1][j-2*vi];假如我们选择k个的话那么就应该写为f[i-1][j-k*vi]那么我们最终的答案就应该在这些集合之中。 所以f(i,j) f(i-1 , j) f(i-1 , j - v) f(i-1 , j - 2v) ........f(i-1 , j - (j/v)*v); 所以f(i,j-v) f(i-1 , j - v) f(i-1 , j - 2*v) f(i-1 , 3*v) ........f(i-1 , j - (j/v)*v); 由上述两个式子我们可以知道如果将 j 替换成 j-vi 两个式子非常相似。f[ i ] [ j ] f[ i -1][ j ] f[ i ][ j - vi ] ; 第三书写主函数构建整体架构 输入值更新我们的初始状态f[0][0] 1。为什么等于1因为围绕我们的定义只从前i个货币中选择总金额不超过 j 的方案的集合。所以f[0][0]表示的是在前0个货币中选总金额为0时的方案数为1因为都不选也是一种方案。 for循环输入货币的面额for循环去遍历金额的大小从0开始根据上图的公式我们可以推断出来f[i][j] f[i-1][j] f[i][j-x];所以利用此公式我们就可以得出答案。但是注意一个问题选择一个选择两个是在金额大于我们的货币面值的情况下才可以选假如答案的金额都要小于货币面额的话就不可以选了 。所以加一个判断只有j金额 x货币面额才可以去选择。
for(int j 0 ; j m ; j ){f[i][j] f[i-1][j];if(j x) f[i][j] f[i][j-x];}
01背包从后往前完全背包从前往后
代码
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 30 , M 10010;
typedef long long LL;LL n , m;
LL f[N][M];int main()
{cinnm;f[0][0] 1;for(int i 1 ; i n ; i ){int x ;cinx;for(int j 0 ; j m ; j ){f[i][j] f[i-1][j];if(j x) f[i][j] f[i][j-x];}}coutf[n][m];return 0;
}
