我们来讲一讲完全背包

完全背包是有n种物品，每个物品有无限个，背包的重量为V，接下来每个背包重量为w[i]，价值为v[i]，求最大总价值。

其实这和01背包在代码上十分相似，思路也很类似

只是这里是有无限个物品

状态转移方程就很容易得出

dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i])    (0<=k*w[i]<=V)

由01背包可以把方程优化成

dp[j]=max(dp[j],dp[j-w[i]]+v[i])    (j=w[i];j<=V;j++)

这里和01背包有不同了，01背包是倒序，这里是顺序

为什么呢？

因为完全背包是由小的状态递推出的大状态

所以需要顺序递推

不多说了

贴代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
           using namespace std;int n,V,dp[1010],v[1005],w[1005];int main(){    scanf("%d %d",&V,&n);     for(int i=1;i<=n;i++)    {        scanf("%d %d",&w[i],&v[i]);    }    for(int i=1;i<=n;i++)    {        for(int j=w[i];j<=V;j++)        {            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);        }    }    printf("%d\n",dp[V]);}
         
        
       
      
     

我太菜了