动态规划之背包九讲

背包九讲

背包九讲链接：https://www.cnblogs.com/jbelial/articles/2116074.html

01背包：

题目链接：https://www.acwing.com/problem/content/2/

二维数组优化前：

 1 #include <iostream>
 2
 3
 4
 5 using namespace std;
 6
 7 const int N = 1e3 + 10;
 8 int v[N], w[N];
 9 int f[N][N];
10
11 int main() {
12     int N, V;
13     cin >> N >> V;
14     for (int i = 1; i <= N; i++)    cin >> v[i] >> w[i];
15     for (int i = 1; i <= N; i++) {
16         for (int j = 1; j <= V; j++) {
17             f[i][j] = f[i - 1][j];
18             if (j >= v[i])  f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
19         }
20     }
21     cout << f[N][V] << endl;
22     return 0;
23 }

View Code

优化后：

#include <iostream>
#include <algorithm>


using namespace std;

const int N = 1e3 + 10;
int v[N], w[N];
int f[N];

int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++)    cin >> v[i] >> w[i];
    for (int i = 1; i <= N; i++)
        for (int j = V; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[V] << endl;
    return 0;
}

View Code

完全背包：

题目链接：https://www.acwing.com/problem/content/3/

优化前：

#include <iostream>


using namespace std;

const int maxn = 1e3 + 10;
int v[maxn], w[maxn];
int f[maxn][maxn];

int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++)    cin >> v[i] >> w[i];
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= V; 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][V] << endl;
    return 0;
}

View Code

优化后：

#include <iostream>


using namespace std;

const int N = 1e3 + 10;
int v[N], w[N];
int f[N];

int main() {
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; i++)    cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= V; j++)
            if (j >= v[i])  f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[V] << endl;
    return 0;
}

View Code

多重背包：

题目链接：https://www.acwing.com/problem/content/4/

数据范围小，不用优化：