经典算法

背包-01背包

有 N 件物品，已知第 i 件物品的重量和价值分别对应为 wᵢ 和 vᵢ 。（不可分割，要么取，要么不取）。有一背包，能装下的重量为 C，问如何选若干件物品，总重量不超过C，总价值达到最大。

【输入描述】

第一行输入背包容量 C 和物品数量 N；然后每行输入对应物品的重量和价值。

【输出描述】

输出背包能装的最大总价值。

【输入样例】

10 4
3 1
4 5
5 6
7 9
【输出样例】

11
【参考程序】

// 小牛编程
#include <iostream>
using namespace std;

int w[105], v[105], dp[105][1005];

int main() {
    int C, N;
    cin >> C >> N;

    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> v[i];
    }

    // 01背包状态方程
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= C; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j - w[i] > 0) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
            }
        }
    }

    cout << dp[N][C] << endl;

    return 0;
}

【滚动数组实现】

// 小牛编程
#include <iostream>
using namespace std;

int w[105], v[105], dp[1005];

int main() {
    int C, N;
    cin >> C >> N;

    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> v[i];
    }

    for (int i = 1; i <= N; i++) {
        for (int j = C; j >= 0; j--) {
            if (j - w[i] > 0) {
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
    }

    cout << dp[C] << endl;

    return 0;
}