01背包

01背包
$方法1，朴素：$

#include <iostream>
using namespace std;
const int N = 1010;
int n,m;
int dp[N][N];
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int w,v;
        cin >> w >> v;
        for (int j = 0;j <= m;j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= w) dp[i][j] = max (dp[i][j],dp[i-1][j-w]+v);
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

$时间复杂度(O(mn))$
$空间复杂度(O(mn))$

$方法2，空间优化：$

#include <iostream>
using namespace std;
const int N = 1010;
int n,m;
int dp[N];
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int w,v;
        cin >> w >> v;
        for (int j = m;j >= w;j--) dp[j] = max (dp[j],dp[j-w]+v);
    }
    cout << dp[m] << endl;
    return 0;
}

$时间复杂度(O(mn))$
$空间复杂度(O(m))$

习题：

采药
装箱问题
宠物小精灵之收服
数字组合
开心的金明

完全背包

完全背包
$方法1，朴素：$

#include <iostream>
using namespace std;
const int N = 1010;
int n,m;
int dp[N][N];
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int w,v;
        cin >> w >> v;
        for (int j = 0;j <= m;j++) {
            for (int k = 0;k*w <= j;k++) {
                dp[i][j] = max (dp[i][j],dp[i-1][j-k*w]+k*v);
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

$时间复杂度(O(m^2n))$
$空间复杂度(O(mn))$

$方法2，时间优化：$

#include <iostream>
using namespace std;
const int N = 1010;
int n,m;
int dp[N][N];
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int w,v;
        cin >> w >> v;
        for (int j = 0;j <= m;j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= w) dp[i][j] = max (dp[i][j],dp[i][j-w]+v);
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

$时间复杂度(O(mn))$
$空间复杂度(O(mn))$

$方法3，空间优化：$

#include <iostream>
using namespace std;
const int N = 1010;
int n,m;
int dp[N];
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int w,v;
        cin >> w >> v;
        for (int j = w;j <= m;j++) dp[j] = max (dp[j],dp[j-w]+v);
    }
    cout << dp[m] << endl;
    return 0;
}

$时间复杂度(O(m))$
$空间复杂度(O(mn))$

习题：

买书
货币系统

多重背包

多重背包I
多重背包II
$方法1，朴素：$

#include <iostream>
using namespace std;
const int N = 1010;
int n,m;
int dp[N][N];
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int w,v,s;
        cin >> w >> v >> s;
        for (int j = 0;j <= m;j++) {
            for (int k = 0;k <= s && k*w <= j;k++) {
                dp[i][j] = max (dp[i][j],dp[i-1][j-k*w]+k*v);
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

$时间复杂度(O(mns))$
$空间复杂度(O(mn))$

$方法2,空间优化：$

#include <iostream>
using namespace std;
const int N = 1010;
int n,m;
int dp[N];
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int w,v,s;
        cin >> w >> v >> s;
        for (int j = m;j >= w;j--) {
            for (int k = 0;k <= s && k*w <= j;k++) {
                dp[j] = max (dp[j],dp[j-k*w]+k*v);
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}

$时间复杂度(O(mns))$
$空间复杂度(O(m))$

$方法3，二进制优化：$

#include <iostream>
using namespace std;
const int N = 25010,M = 2010;
int n,m;
int v[N],w[N];
int dp[M];
int main () {
    cin >> n >> m;
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        int a,b,s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s) {
            cnt++;
            w[cnt] = a*k;
            v[cnt] = b*k;
            s -= k;
            k *= 2;
        }
        if (s > 0) {
            cnt++;
            w[cnt] = a*s;
            v[cnt] = b*s;
        }
    }
    n = cnt;
    for (int i = 1;i <= n;i++) {
        for (int j = m;j >= w[i];j--) {
            dp[j] = max (dp[j],dp[j-w[i]]+v[i]);
        }
    }
    cout << dp[m] << endl;
    return 0;
}

$空间复杂度(O(mnlog_s))$
$时间复杂度(O(m))$

习题：

庆功会

混合背包

混合背包
$方法1，空间优化：$

#include <iostream>
using namespace std;
const int M = 1010;
int n,m,w,v,s;
int dp[M];
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> w >> v >> s;
        if (s == 0) {
            for (int j = m;j >= w;j--) dp[j] = max (dp[j],dp[j-w]+v);
        }
        else {
            if (s == -1) s = 1;
            for (int k = 1;k <= s;k *= 2) {
                for (int j = m;j >= k*w;j--) {
                    dp[j] = max (dp[j],dp[j-k*w]+k*v);
                }
                s -= k;
            }
            if (s) {
                for (int j = m;j >= s*w;j--) {
                    dp[j] = max (dp[j],dp[j-s*w]+s*v);
                }
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}

$空间复杂度(O(mns))$
$时间复杂度(O(m))$

二维费用的背包

$方法1，空间优化：$

#include <iostream>
using namespace std;
const int N = 110;
int n,W,M;
int dp[N][N];
int main () {
    cin >> n >> W >> M;
    for (int i = 1;i <= n;i++) {
        int w,m,v;
        cin >> w >> m >> v;
        for (int j = M;j >= m;j--) {
            for (int k = W;k >= w;k--) {
                dp[j][k] = max (dp[j][k],dp[j-m][k-w]+v);
            }
        }
    }
    cout << dp[M][W] << endl;
    return 0;
}

$时间复杂度O(mnw)$
$空间复杂度O(mw)$

习题：

潜水员

分组背包

分组背包

$方法1，朴素：$

#include <iostream>
using namespace std;
const int N = 110;
int n,m;
int s[N],w[N][N],v[N][N];
int dp[N];
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> s[i];
        for (int j = 1;j <= s[i];j++) cin >> w[i][j] >> v[i][j];
    }
    for (int i = 1;i <= n;i++) {
        for (int j = m;j >= 0;j--) {
            dp[i][j] = dp[i-1][j];
            for (int k = 1;k <= s[i];k++) {
                if (w[i][k] <= j) dp[i][j] = max (dp[i][j],dp[i-1][j-w[i][k]]+v[i][k]);
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

$空间复杂度(O(mns))$
$时间复杂度(O(m))$

$方法2，空间优化：$

#include <iostream>
using namespace std;
const int N = 110;
int n,m;
int w[N][N],v[N][N],s[N];
int dp[N];
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> s[i];
        for (int j = 1;j <= s[i];j++) cin >> w[i][j] >> v[i][j];
    }
    for (int i = 1;i <= n;i++) {
        for (int j = m;j >= 0;j--) {
            for (int k = 1;k <= s[i];k++) {
                if (w[i][k] <= j) dp[j] = max (dp[j],dp[j-w[i][k]]+v[i][k]);
            }
        }
    }
    cout << dp[m] << endl:
    return 0;
}

$空间复杂度(O(mns))$
$时间复杂度(O(m))$

习题：

金明的预算方案
机器分配

有依赖的背包问题

有依赖的背包问题

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010,mod = 1e9+7;;
int n,m;
int dp[N],cnt[N];
int main () {
    cin >> n >> m;
    for (int i = 0;i <= m;i++) cnt[i] = 1;
    for (int i = 1;i <= n;i++) {
        int w,v;
        cin >> w >> v;
        for (int j = m;j >= w;j--) {
            int value = dp[j-w]+v;
            if (value > dp[j]) {
                dp[j] = value;
                cnt[j] = cnt[j-w];
            }
            else if (value == dp[j]) cnt[j] = (cnt[j]+cnt[j-w])%mod;
        }
    }
    cout << cnt[m] << endl;
    return 0;
}

$空间复杂度(O(mn))$
$时间复杂度(O(m))$