背包典型例题-526互联

一、01背包

for(int i=V;i>=c[i];--i){
	dp[i]=max(dp[i], dp[i-c[i]]+w[i])
}

hdu3466。这个题要考虑dp的无后效性质，简单来说，就是dp与物品排布有关的时候，我们应该选择最优的那一个。如果单独选择

i,j都没有问题的时候。如果先选i再选j可以做到，反之不可以。那么说明pi+qj < pj + qi =》qi-pi > qj - pj。所以应该按照q-p排序之后在01背包。

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const int N  = 1e5 + 5;

int n, m;

struct node{
    int x, y, z;
    bool operator<(const node& a1)const{
        return y-x < a1.y-a1.x;
    }
};

node a[N];

int dp[1005];

int main(){
    while(cin >> n >> m){
        memset(dp, 0, sizeof(dp));
        for(int i=1;i<=n;++i){
            cin >> a[i].x >> a[i].y >> a[i].z;
        }
        sort(a+1, a+n+1);
        for(int i=1;i<=n;++i){
            for(int j=m;j>=a[i].y;--j){
                dp[j]=max(dp[j], dp[j-a[i].x]+a[i].z);
            }
        }

        int ans=0;
        for(int i=0;i<=m;++i){
            ans=max(ans,dp[i]);
        }
        cout<<ans<<endl;
    }
    
    return 0;
}

二、完全背包

与01背包的一维写法不同，现在的转移方程是：

for(int j=c[i];j<=V;++j){
	dp[j]=max(d[j],dp[j-c[i]]);
}

https://www.luogu.com.cn/problem/P1853

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const int N  = 5e4 + 5;

LL n, m, T;

LL a[15][3];

LL dp[N];

int main(){
    cin >> n >> T >> m;
    for(int i=1;i<=m;++i){
        cin >> a[i][0] >> a[i][1];
        a[i][0] /= 1000;
    }

    for(int i=1;i<=T;++i){
        int tmp = n / 1000;
        int o=n;
        for(int j=0;j<=tmp;++j)dp[j]=0;
        for(int j=1;j<=m;++j){
            for(int k=a[j][0];k<=tmp;++k){
                dp[k]=max(dp[k], dp[k-a[j][0]]+a[j][1]);
            }
        }
        for(int k=0;k<=tmp;++k)n=max(n, o+dp[k]);
    }

    cout<<n<<endl;
    
    return 0;
}

三、多重背包

http://101.43.147.120/p/P1025

跟01背包一样，但是需要枚举一下第i类需要多少个。

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const int N  = 1e5 + 5;

int n, m, T;

int a[N][3];

int dp[1005];

int main(){
    cin >> n >> m >> T;

    for(int i=1;i<=n;++i){
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }

    for(int i=1;i<=n;++i){
        a[i][2] = T / a[i][2]; 
    }

    for(int i=1;i<=n;++i){
        for(int j=m;j>=a[i][1];--j){
            for(int k=1;k<=a[i][2];++k){
                if(j<k*a[i][1])continue;
                else{
                    dp[j]=max(dp[j], dp[j-k*a[i][1]] + k * a[i][0]);
                }
            }
        }
    }

    int ans=0;
    for(int i=0;i<=m;++i)ans=max(ans,dp[i]);
    cout<<ans<<endl;
    
    return 0;
}

此外，还有需要二进制优化的多重背包。其核心思想就是在将多重背包的件数约束转化为一系列二进制表示。例如上述的题目我可以这么写。结果就是会跑到快很多。

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const int N  = 1e5 + 5;

int n, m, T;

LL a[N][3];

LL dp[1005];

int main(){
    cin >> n >> m >> T;

    for(int i=1;i<=n;++i){
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }

    for(int i=1;i<=n;++i){
        a[i][2] = T / a[i][2]; 
    }

    for(int i=1;i<=n;++i){
        for(int s=1;s<=a[i][2];s<<=1){
            for(int j=m;j>=s*a[i][1];--j){
                dp[j]=max(dp[j], dp[j-s*a[i][1]] + s * a[i][0]); 
            }
            a[i][2]-=s;
        }
        if(a[i][2]>0){
            for(int j=m;j>=a[i][2]*a[i][1];--j){
                dp[j]=max(dp[j], dp[j-a[i][2]*a[i][1]] + a[i][2]*a[i][0]);
            }
        }
    }
    

    LL ans=0;
    for(int i=0;i<=m;++i)ans=max(ans,dp[i]);
    cout<<ans<<endl;
    
    return 0;
}