【动态规划】完全背包问题求解方案数及其优化原理C++

• • 前言
  • 例题
  • 例题分析
  • 完全背包问题
  • • 1.几维背包
    • 2.状态表示
    • 3.状态划分（重点)
    • • （1）当选0个第i个物品的时候
      • （2）当选1，2，...，k，...，j/w[i]个第i个物品的时候
      • （3）汇总以及优化
  • 最后的一维优化
  • AC代码

本文主要是根据例题讲解完全背包问题的一般二维写法以及一维优化的原理

钱币兑换

在一个国家仅有1分，2分，3分硬币，将钱N分 (N<32768) 兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

根据题意分析，该题为完全背包问题，因为每一种的硬币有无限个，最多可以选（当前总面值为n时）n/w[i]个，其中w数组表示存的第i种硬币的面值。

首先思考该问题用几维，因为涉及到每一种硬币的面值还有总面zhi值，所以用两维。

定义一个二维数组f[N][N],那么f[i][j]的含义是什么？
根据题意，f[i][j]表示的是从1~i种面值的钱币里面选，使得总面值为N的方案数的集合
集合的属性是方案数

划分的依据是最后一个不同点，这里最后一个不同点是第i种硬币的选与不选，由题意知第i种硬币可以选0，1，2，…,k,…，j/w[i]个，此时分情况讨论。

就是说不选第i个物品，此时f[i][j]表示从所有从前1~i-1个物品当中选，使得总面值为j的方案数。
根据定义得出，此时为f[i-1][j]。

此时的所有方案大致为：

1. 前i-1个物品任意选，第i个物品选k*w[i]个
2. 前i-1个物品任意选，第i个物品选k*w[i]个
3. …
   此时可以发现所有方案中前面的部分不一样，后面的选第i个物品都选了k个，这个时候我们把前面跟后面分开，这时f[i][j]就是（由于是方案数，所以加上跟减去一个定值不改变方案数）跟前面有关。
   再来思考前面，前i-1个物品任意选就是从所有1~i-1个物品当中选，使得总面值不超过j-kw[i]的方案数，根据f[i][j]的定义，可以得出是f[i-1][j-kw[i]].此时所有种类不重不漏的划分完毕
   但是有一个问题，此时的算法时间复杂度为O(n^3),时间复杂度并未降低，这时我们需要再次优化时间复杂度。

此时得到的f[i][j]为
f[i][j]=f[i-1][j]+f[i-1][j-w[i]]+f[i-1][j-2w[i]]+…+f[i-1][j-(j/w[i])*w[i]]
这时我们根据换元发现
f[i][j-w]=f[i-1][j-w]+f[i-1][j-2w]+…+f[i-1][j-(j/w[i])*w[i]],此时的
第二个长式子后面的那部分跟第一行长式子f[i-1][j]后面的那部分完全一样，此时可以用f[i][j-w]来代替，这时的f[i][j]=f[i-1][j]+f[i][j-w[i]]。
至此，时间复杂度被优化为O(nm)
这就是完全背包问题的一般优化方法。

前面的优化是对时间复杂度的优化，不能算作最终的优化，此时再次对空间进行优化，对空间的优化就是对代码进行等价变形
此时
for(int i=1;i<=3;i++){//枚举钱币种数，相当于枚举w[i]
for(int j=0;j<=n;j++){//枚举总面值
f[i][j]=f[i-1][j]+f[i][j-i];
}
}
循环中把二维变成一维即可

        #include

        using namespace std;
        const int N=40010;
        int f[N];
        int n;
        int main(){
            cin>>n;
            f[0]=1;
            for(int i=1;i<=3;i++){
                for(int j=i;j<=n;j++){
                    f[j]=f[j] +f[j-i];//此时要保证j-i>=0,因为当总面值小于该面值的钱币的时候，不能选该面值的钱币
                }
            }
            cout< 
后续遇到问题会继续更新，希望各位小伙伴点点关注吧！我会继续努力的！！！