背包

模板背包

• 基础的意识得有，变个形也得会做

• 以下是模板(以下模板除了1e5以上数据均会超时）

• 01背包

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,dp[N];
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--)
        dp[j]=max(dp[j],dp[j-v]+w);
    }
    cout<<dp[m];
    return 0;
}

• 完全背包(可选无数次)

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,dp[N];
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j=v;j<=m;j++)
        {
            dp[j]=max(dp[j],dp[j-v]+w);
        }
    }
    cout<<dp[m];
    return 0;
}

• 多重背包

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,dp[N];
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        for(int j=1;j<=s;j++)
        for(int k=m;k>=v;k--)
        dp[k]=max(dp[k],dp[k-v]+w);
    }
    cout<<dp[m];
    return 0;
}

例题：

小精灵

二维费用背包

分析：

• 花费1：精灵球数量
• 花费2：皮卡丘体力值
• 价值：小精灵的数量

状态表示：$dp[i][j][k]$ 所有只从前 $i$ 个物品中选，且花费1不超过 $j$ ，花费2不超过 $k$ 的选法的最大价值（这里价值即为数量）。

状态计算：$dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-v1[i]][k-v2[i]]+1)$

输出和边界：
- 最多可以收服 $dp[k][N][M]$
- 枚举第三维来看哪个最小体力达到最大收服数量 ### 代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1010,M=510;//费用1和费用2 
int V1,V2,dp[N][M],k;
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>V1>>V2>>k;
    for(int i=0,v1,v2;i<k;i++)
    {
        cin>>v1>>v2;
        for(int j=V1;j>=v1;j--)
        for(int k=V2;k>=v2;k--)
        dp[j][k]=max(dp[j][k],dp[j-v1][k-v2]+1);
    }
    int n=V2;
    cout<<dp[V1][V2]<<' ';
    //从初始体积开始枚举
    while(n>0&&dp[V1][n-1]==dp[V1][V2])n--;
    //这里求出的n是体力最少消耗多少 
    cout<<V2-n; 
    return 0;
}

求体积剩余还是有问题（之后解决）

方案数背包

正整数拆分

分析

这里任意的数拆分即可，而且不限制顺序，明显完全背包，从[1,n]的每个数字作为费用去转移即可
如果拆分的数字时2的幂次的话，枚举次数时要倍增 i<<=1

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int M=2147483648;
const int N=1e5+10;
int n,dp[N];
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    dp[0]=1;
    //完全背包，无限次使用 
    for(int i=1;i<=n;i++)
    //这里的价值就是[1,n]的每一个数字 
    for(int j=i;j<=n;j++)
    dp[j]=(dp[j]+dp[j-i])%M;
    cout<<dp[n]-1;
    return 0;
}