01 背包问题

1 表示使用 1 次或者使用 0 次

DP分析法

• 状态表示 f[i][j]
  • 集合：所有数量为 i ，总体积不超通过 j 的物品的选法集合，不能重复选择物品
  • 属性：最大价值
• 状态计算
  • 所有不选择第 i 个物品方案中的最大值 f[i-1][j]
  • 所有选择第 i 个物品方案中的最大值 f[i-1][j-v[i]]+w[i]

朴素代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m;
int w[N],v[N];
int f[N][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=0;j<=m;j++){
            f[i][j] = f[i-1][j];
            if(j>=v[i]) f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][m];
    return 0;
}

优化空间后代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m;
int w[N],v[N];
int f[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--){
            f[j] = max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}

优化思路

由于j是从大到小循环的，假设j = 5； j >= 2; j –; 也就是这一层（第i层）会先算出来f[5],（注意这个时候，第i层正在算f[5], 也就是说第i层没有更新f[4] f[3]，也就是此时的f[4] f[3] 是i - 1层的）那么算f[5]要用到比他更小的f[4]或者f[3]也就是i - 1层的了。

完全背包问题

DP分析法

• 状态表示 f[i][j]
  • 集合：所有数量为i，总体积不超过j的物品的选法集合，能重复选择物品
  • 属性：最大价值
• 状态计算
  • 不选第i个物品 f[i-1][j]
  • 所有选i个物品最大值 f[i][j-v]+w

推导方式

朴素代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N], w[N];
int n, m;
int f[N][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 = 1; j <= m; j ++ ){
            f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m];
    return 0;
}

优化后代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N], w[N];
int n, m;
int f[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 ++ ){
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m];
    return 0;
}