01背包问题

来源： acwing

题目内容

有N件物品和一个容量是V的背包。每件物品只能使用一次。

第i件物品的体积是v_i，价值是w_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有N行，每行两个整数v_i，w_i，用空格隔开，分别表示第i件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0 < N，V ≤ 1000

0 < v_i，w_i ≤ 1000

输入样例

4 5

1 2

2 4

3 4

4 5

输出样例：

8

代码实现

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
int f[N];
int V[N], W[N];

int main() {
    int n, v;
    
    cin >> n >> v;
    for(int i = 1; i <= n; i++) {
        cin >> V[i] >> W[i];
    }
    // i 表示第i个物体，j表示体积，f[j]表示在体积为j时所能装下的最大价值
    for(int i = 1; i <= n; i++) {
        for(int j = v; j >= V[i]; j--) {
            f[j] = max(f[j - V[i]] + W[i], f[j]);
        }
    }
    cout << f[v] << endl;
    
    return 0;
}

完全背包问题

来源： acwing

题目内容

有N件物品和一个容量是V的背包。每种物品都有无限件可用。

第i件物品的体积是v_i，价值是w_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有N行，每行两个整数v_i，w_i，用空格隔开，分别表示第i件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0 < N，V ≤ 1000

0 < v_i，w_i ≤ 1000

输入样例

4 5

1 2

2 4

3 4

4 5

输出样例：

10

代码实现

#include <iostream>
#include <algorithm>
using namespace std;

const int S = 1010;
int f[S];

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

多重背包问题 1

题目来源： acwing 4

题目内容

有N种物品和一个容量是V的背包。

第i种物品最多有s_i件，每件体积是v_i，价值是w_i。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有N行，每行三个整数v_i，w_i，s_i，用空格隔开，分别表示第i种物品的体积，价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围

0 < N，V ≤ 100

0 < v_i，w_i，s_i ≤ 100

输入样例

4 5

1 2 3

2 4 1

3 4 3

4 5 2

输出样例：

10

代码实现

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;
int f[N];

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        int v, w, s;
        cin >> v >> w >> s;

        for(int j = m; j >= v; j--) {
            for(int k = 1; k <= s && j >= k * v; k++) {
                f[j] = max(f[j], f[j - k * v] + k * w);
            }
        }
    }
    cout << f[m] << endl;
    
    return 0;
}