动态规划

标签：typedef 背包 int cin long tie 动态 规划

背包问题

01背包

AcWing 2. 01背包问题

二维：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=1e3+5;
int n,m,v[N],w[N],f[N][N];
int main()
{
    cin.tie(0),cout.tie(0);
    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])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][m];
    return 0;
}

View Code

一维：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=1e3+5;
int n,m,v[N],w[N],f[N];
int main()
{
    cin.tie(0),cout.tie(0);
    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){
                f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}

View Code

 

完全背包

AcWing 3. 完全背包问题

二维：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=1e3+5;
int n,m,v[N],w[N],f[N][N];
int main()
{
    cin.tie(0),cout.tie(0);
    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){
            if(j<v[i])f[i][j]=f[i-1][j];
            else f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][m];
    return 0;
}

View Code

一维：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=1e3+5;
int n,m,v[N],w[N],f[N];
int main()
{
    cin.tie(0),cout.tie(0);
    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){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}

View Code

 

多重背包

AcWing 4. 多重背包问题

 

 

分组背包

 

标签：typedef,背包,int,cin,long,tie,动态,规划
From： https://www.cnblogs.com/bible-/p/17097013.html