完全背包问题（超级详细地讲解优化过程）

完全背包问题

• 一、问题描述
• 二、思路分析
• • 1、状态转移方程
  • 2、循环设计
  • 三、代码模板
  • • 1、朴素版
    • 2、优化版
    • • （1）时间优化
      • （2）���间优化

        一、问题描述

        二、思路分析

        完全背包和01背包的区别就在于01背包中，每个物品只能选择一次，而完全背包问题中，每个物品可以选择无限次。如果大家没有看过之前01背包的讲解的话，建议大家先去看看作者之前写的01背包问题，传送门：01背包问题

        那么很明显，这道题符合动态规划的三个性质：最优子结构，重叠子问题，无后效性。因此，我们可以利用动态规划的思路去解决这道题。这三个性质的分析和01背包是一样的。

        那么想要利用动态规划的思路来解决这道题的话，我们需要做两件事情：

        1、构建当前问题和子问题之间的关系：书写状态转移方程。

        2、设计循环，记录每一个子问题的最优解。

        1、状态转移方程

        状态转移方程的作用是我们通过数学表达式来达到缩小问题规模。所以，我们需要用子问题来解决当前状态。而在上一节01背包问题中，我们曾经介绍过，对于背包问题中状态转移方程的书写，我们的方式是：活在当下。

        我们面前要做的选择就是第i个物品，你到底是选还是不选，如果选你能选多少？

        很明显，只要在容量允许的范围内，我们可以选很多个，最后我们在各种方案内选出一个最大值。

        如下所示：

        f ( i , j ) = m a x { f ( i − 1 , j ) f ( i − 1 , j − v [ i ] ∗ 1 ) + w [ i ] ∗ 1 . . . f ( i − 1 , j − v [ i ] ∗ k ) + w [ i ] ∗ k k ∗ v [ i ] ≤ j f(i,j)=max \begin{cases} f(i-1,j)\\ f(i-1,j-v[i]*1)+w[i]*1\\ ...\\ f(i-1,j-v[i]*k)+w[i]*k&k*v[i]\leq j \end{cases} f(i,j)=max⎩ ⎨ ⎧​f(i−1,j)f(i−1,j−v[i]∗1)+w[i]∗1...f(i−1,j−v[i]∗k)+w[i]∗k​k∗v[i]≤j​

        2、循环设计

        循环的设计其实就是为了有条不紊地逐渐计算出规模不断增大地子问题。完全背包的循环设计和01背包的循环设计是一致的。我们逐一枚举1个物品时，各个容量下的最优解，2个物品时，各个容量下的最优解，直到n个物品下，各个容量下的最优解。

        三、代码模板

        1、朴素版

        #include
        using namespace std;
        const int N=1010;
        int f[N][N],v[N],w[N];
        int n,m;
        int main()
        {
            cin>>n>>m;
            for(int i=1;i
                for(int j=0;j
                    for(int k=0;k*v[i]
                        f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);
                    }
                }
            }
            coutf[i][j]max(f[i][j],f[i][j−v[i]]+w[i])​j
            cinnm;
            for(int i=1;i
                for(int j=0;j
                    f[i][j]=f[i-1][j];
                    if(j=v[i])
                    f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
                }
            }
            cout
            cinnm;
            for(int i=1;i
                scanf("%d%d",v+i,w+i);
            }
            for(int i=1;i
                for(int j=0;j
                    if(j=v[i])
                    f[j]=max(f[j],f[j-v[i]]+w[i]);
                }
            }
            cout