动态规划DP

表示方式分为状态表示和状态计算

状态表示可以从两个角度来考虑，分为集合和集合属性

集合属性分为数量、最大值、最小值

image-20210313211822057

0-1背包问题

有一个背包，最大容量为X
有N件物品，体积和价值分别为V[i]和W[i]
每件物品只能选一次，求该背包能装多大价值的的物品### 递归
每件物品$$\begin 被选择 \ 被跳过 \end$$

  1. 初始化时，当前背包从0号物品开始选，此时函数需要两个参数，参数1为当前选择的物品，参数2为当前占用的容量
  2. 当一个物品被选择时，可以表示为f(下个物品, 当前的容量 + 选择的物品的容量) + 当前物品的价值
  3. 当一个物品不被选择时，可以表示为f(下个物品, 当前的容量)
  4. 当物品不存在时，返回0
  5. 当背包装不下时，可以尝试着看一下下一个物品是否能被放入，此时函数返回为f(下个物品, 当前的容量)
#include <bits/stdc++.h>
using namespace std;
int n, v;
pair<int, int> w[1100];
int dp(int j, int now)
{
    if (j >= n)
    {
        return 0;
    }
    if (now + w[j].first > v)
    {
        return dp(j + 1, now);
    }
    return max(dp(j + 1, now + w[j].first) + w[j].second, dp(j + 1, now));
}
int main()
{
    cin >> n >> v;
    for (int i = 0; i < n; i++)
    {
        int a, t;
        cin >> a >> t;
        w[i] = {a, t};
    }
    cout << dp(0, 0) << endl;
    return 0;
}

递归 + 数组

由以上代码可见，每次递归都有大量的重复计算数据，可以用一个数组将这个过程模拟出来

非递归

总共有4件物品，容量为5的背包
4 5
以下为每件物品的信息
体积和价值
1 2
2 4
3 4
4 5

背包的状态表示为f(i,j)，其中i为可以在几种物品中进行选择，j表示剩余的体积，

每件物品$$\begin 被选择 \ 被跳过 \end$$

过程

image-20210313223032945

开辟两个数组，f[N][N]、W[N]---重量和V[N]--价值

此时可知f(i,j)=$$\beginf(i-1,j)--放不下去了或者不放\f(i-1,j-W[i])+V[i]---放入\end$$

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N],f[N][N],vv;
int main()
{
    int n;
    cin>>n>>vv;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=vv;j++)
        {
            if(j<v[i])
                f[i][j]=f[i-1][j];
            else
                f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][vv];
    return 0;
}

完全背包问题

有一个背包，最大容量为X
有N件物品，体积和价值分别为V[i]和W[i]
每件物品可以选多次，求该背包能装多大价值的的物品
状态转移方程，dp[i][j]

其中i的含义为在前i件物品中选，体积不超过j

因为每件物品可以被选择0次或者多次，具体的次数是未知的，但此时被选的体积不能超过还剩的体积

所以

for(int k=0;k*v[i]<=j;k++)

此时的j为剩余的容量

因此

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

朴素版代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int main()
{
    int n,m;
    int v[N],w[N],dp[N][N];
    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=0;j<=m;j++)
            for(int k=0;k*v[i]<=j;k++)
                dp[i][j]=max(dp[i-1][j-k*v[i]]+k*w[i],dp[i][j]);
    cout<<dp[n][m];
    return 0;
}
```#### 优化
可以优化为二维的
```c++
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int main()
{
    int n,m;
    int v[N],w[N],dp[N][N];
    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=0;j<=m;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j>=v[i])
            	dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
        }
    cout<<dp[n][m];
    return 0;
}
```### 多重背包问题
> 有一个背包，最大容量为**X**  
> 有**N**件物品，最多的数量、体积和价值分别为`S[i]`、`V[i]`和`W[i]`  
> 每件物品最多可以选`S[i]`次，求该背包能装多大**价值**的的物品```c++  
#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int vv[N],dp[N][N],w[N],s[N];
int main()
{
    int n,v;
    cin>>n>>v;
    for(int i=1;i<=n;i++)
        cin>>vv[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=v;j++)
            for(int k=0;k*vv[i]<=j&&k<=s[i];k++)
                {
                    dp[i][j]=max(dp[i][j],dp[i-1][j-k**vv[i]]+k**w[i]);
                }
    cout<<dp[n][v];
    return 0;
}

Q.E.D.

念念不忘，必有回响。