DP之背包问题

题目一

image-20250202212733430

方法一
#include <bits/stdc++.h>
using namespace std;


const int N = 1e3+10;

int n,m;
int v[N],w[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++) {
            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];
}
方法二
#include <bits/stdc++.h>
using namespace std;


const int N = 1e3+10;

int n,m;
int v[N],w[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 = n;i >= 1;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+1][j-v[i]] + w[i]);
        }
    }

    cout << f[1][m];
}
方法三
#include <bits/stdc++.h>
using namespace std;


const int N = 1e3+10;

int n,m;
int v[N],w[N];
int f[N][N];
int g[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 >= 0;j--) {
            if (j >= v[i]) g[j] = max(g[j],g[j-v[i]] + w[i]);
        }
    }

    cout << g[m];
}

题目二

image-20250202222500626

#include <bits/stdc++.h>
using namespace std;


const int N = 1e3+10;

int n,m,o;
int v[N],w[N],ww[N];
int f[N][110][110];


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

    for (int i = 1;i <= n;i++) {
        cin >> v[i] >> w[i] >> ww[i];
    }
    for (int i = n;i >= 1;i--) {
        for (int j = 0;j <= m;j++) {
            for (int k = 0;k <= o;k++) {
                if (j < v[i] || k < w[i]) {
                    f[i][j][k] = f[i+1][j][k];
                }else {
                    f[i][j][k] = max(f[i+1][j][k],f[i+1][j-v[i]][k-w[i]] + ww[i]);
                }
            }
        }
    }
    cout << f[1][m][o];
}

题目三

image-20250205232429849

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int n,m;
int v[N],w[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++) {
            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;
}