动态规划基础：背包问题(优化写法)

动态规划：状态表示（集合：f(i,j) 的含义；属性：求Max (例)）+状态计算（如何进行状态转移、计算）
由于仅做复习用，具体推导未详细写出。

一：01背包问题

每个物品有且只有一个。

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int f[N];
int v[N],w[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=m;j>=v[i];j--) //类似滚动数组原理，j从大到小遍历避免覆盖之前的存值
        {
                f[j]=max(f[j],f[j-v[i]]+w[i]);//上层状态，必选第i件的情况
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

二：完全背包

每个物品有无限个。
【唯一从小到大更新w[i]的题类】

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int f[N],v[N],w[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++) //与01背包解法的唯一区别，从小到大遍历，更新存值
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m]<<endl;
    return 0;
}

三：多重背包问题 II

每个物品给定了数量。
对于每个物品的数量s[i]，用二进制优化了查找，复杂度为O(vwlog2(s))。

#include <bits/stdc++.h>
using namespace std;
const int N=24100; //这里的N是根据n的范围乘上log2(s)得到的
int n,m;
int f[N],v[N],w[N],cnt;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int a,b,s;
        cin>>a>>b>>s;
        int k=1;    //得到所有组合
        while(k<=s) //二进制优化查找
        {
            cnt++;
            v[cnt]=a*k; 
            w[cnt]=b*k;
            s-=k;
            k=k*2;
        }
        if(s>0) //最后剩余的（此时s>2^t && s<2^(t+1)）
        {
            cnt++;
            v[cnt]=a*s;
            w[cnt]=b*s;
        }
    }
    n=cnt;  //不要忘记更新n的范围！！！
    for(int i=1;i<=n;i++)   //用01背包解法即可
        for(int j=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m]<<endl;
    return 0;
}

四：分组背包问题

物品有多组，每组里面有多个物品，但每组内只能选一个物品。

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int f[N],v[N][N],w[N][N],s[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        for(int j=0;j<s[i];j++)
            cin>>v[i][j]>>w[i][j];
    }
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)    //从大到小，避免覆盖
            for(int k=0;k<s[i];k++)    //遍历挑选组内物品
                if(v[i][k]<=j)    //可装
                    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
    cout<<f[m]<<endl;
    return 0;
}