01背包

• 原题链接

闫氏dp分析法：

对于dp[i][j]，状态空间是两个集合，一个是选第i个物品，一个是不选第i个物品
其中不选第i个物品，那没对总体积j无影响
如果选了第i个物品，那么需要保证在选了i-1个物品时，需要有v[i]的空间

#include <iostream>
#include <algorithm>

using namespace std;

const int N=1010;

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

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i],&w[i]);
    }
    
    for(int i=1;i<=n;i++)//枚举物品个数
    {
        for(int j=0;j<=m;j++)//枚举背包体积
        {
            dp[i][j]=dp[i-1][j];//左半边集合
            if(j>=v[i])//右边子集存在的前提下
                dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
                
        }
    }
    
   cout<<dp[n][m]<<endl;
   
    return 0;
}

---

01背包降维

首先去掉[i]与[i-1]看看有没有影响

 for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[j]=dp[j];//左半边集合
            if(j>=v[i])//右边子集存在的前提下
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
                
        }
    }

对于dp[j]=dp[j],左边更新完了等于右边，左边是dp[i-1][j],所以是拿i-1时刻的dp值，更新i时刻的dp值，没问题！
对于dp[][j-v[i]]+w[i],由于j-v[i]<j,所以j的正向遍历导致此时的dp[j-v[i]]已经被更新过一次是第i时刻的，而非第i-1时刻，因此不正确，需要逆向遍历

  for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
                
   cout<<dp[m]<<endl;

---

01背包降维（个人理解）

对于二维降一维，外层循环中的每一个i其实是不需要记录的
所以在第i次循环刚开始时，所有的dp[]都未更新，此时下面的dp[x]记录的是前i-1个物品在容量是x时的最大值(x>=0&&x<=V)

dp[0]	dp[1]	dp[2]	dp[..]	dp[V]

相当于dp[i][x]=dp[i-1][x]或dp=dp[i-1][x-v[i]]+w[i]

• 下面看01背包的1维数组存放的代码

for(int i=1;i<=n;i++)
{
   for(int x=V;x>=v[i];x--)
   {
     dp[x]=max(dp[x],dp[x-v[i]]+w[i]);
   }
}

所以x递减遍历的原因：我们要保证在i时刻求解dp[x]的时候，max比较的
dp[x]项与dp[x-w[i]]+c[i]项必须是i-1时刻的值，

dp[0]	dp[1]	dp[2]	dp[..]	dp[x-w[i]]	dp[...]	dp[x]	dp[....]	dp[V]

假如我们正序遍历，从左往右第一次更新得到的dp[x-w[i]]+c[i],此时它的含义是前i个物品在容量是x-w[i]时的最大值，然后再往后，更新到dp[x]时显然max中的dp[x-w[i]]+c[i]项中的i-1时刻的值已经被覆盖为i时刻的值了，所以不能正序遍历，需要逆序遍历，防止被更新

---

二维费用背包问题（多维01背包问题）

#include <iostream>

using namespace std;

const int N=1010;

int dp[N][N];

int main()
{
    int n,v,m;
    cin>>n>>v>>m;
    for(int i=0;i<n;i++)
    {
        int vi,mi,wi;
        cin>>vi>>mi>>wi;
        for(int j=m;j>=mi;j--)
        {
            for(int k=v;k>=vi;k--)
            {
                dp[j][k]=max(dp[j][k],dp[j-mi][k-vi]+wi);
            }
        }
    }
    cout<<dp[m][v]<<endl;
}