完全背包问题朴素版

状态转移方程（集合划分）：f(i,j)=max(f(i-1,j),f(i-1,j-k*vi)+k*wi)  (k=1,2,...,直到k*vi>j)
                         和0-1背包一样，考虑第i个物品是否装入，不装入就是f(i-1,j)，装入的话要考虑装1个，2个，还是3个，便是f(i-1,j-k*vi)+k*wi)

                         注意：这里实现起来容易出现错误(详见错题本：完全背包)

                         其实，进一步思考，我们可以把状态转移方程化成统一的形式,f(i-1,j)就是f(i-1,j-0*vi)+0*wi
                         于是f(i,j)=max(f(i-1,j-k*vi)+k*wi)

易错点：1.在读入所有物品体积和价值的时候，下标必须从1开始
          因为dp[i][j],v[i],w[i]下标是一个系统的，i=1表示前1个物品,v[1]表示第1个物品的体积，
          所以v[0]表示第0个物品体积，是没有意义的。下标不能从0开始
        2.状态转移方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])是有定义域的，当j<v[i]时dp[i-1][j-v[i]]
          是无意义的

第一种方程代码

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int n,m,v[N],w[N],dp[N][N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
      {
          dp[i][j]=max(dp[i][j],dp[i-1][j]);
          for(int k=1;k*v[i]<=j;k++)//等价于max(dp[i-1][j-k*v[i]+k*w[i]),k=0,1,2,...)
          {
              dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
          }
      }


    cout<<dp[n][m];

    return 0;
}

第二种方程代码

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int n,m,v[N],w[N],dp[N][N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        for(int k=0;k*v[i]<=j;k++)//等价于max(dp[i-1][j-k*v[i]+k*w[i]),k=0,1,2,...
        {
            dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
        }

    cout<<dp[n][m];

    return 0;
}

完全背包问题优化（三层循环降为两层循环）

状态转移方程（集合划分）：f(i,j)=max(f(i-1,j),f(i,j-vi)+wi) 

代码

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int n,m,v[N],w[N],dp[N][N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
      {
          if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);//注意不要忘了状态转移方程的成立条件
          else dp[i][j]=dp[i-1][j];
      }

    cout<<dp[n][m];

    return 0;
}

进一步优化，状态二维变一维

优化思路：在填表的过程中，比如要填f(i,j),只用到了上一个位置f(i-1,j)和同行前面的f(i,j-v[i]),
          我们可以把f(i-1,j)的位置移到f(i,j),使得每次要填f(i,j),的时候,f(i,j)存的都是优化前的f(i-1,j),只要算出来覆盖掉f(i,j)就好了。
          用一维数组，从左至右循环覆盖n次

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int n,m,v[N],w[N],dp[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++)
      for(int j=v[i];j<=m;j++)//j<v[i]时，dp[i][j]=dp[i][j],无意义
      {
          dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
      }

    cout<<dp[m];

    return 0;
}