01背包

每件物品只能使用一次

01背包的理解

未命名图片

引用自b站的评论

1

二维解法：

#include<iostream>

using namespace std;
//二维解法

const int N = 1010;
int dp[N][N];
int w[N];
int v[N];

int main() {
    int n, weight;
    scanf("%d%d", &n, &weight);

    for (int i = 1; i <= n; i++)
        scanf("%d%d", &w[i], &v[i]);

    for (int i = 1; i <= n; i++)
        for (int j = weight; j >= 1; j--)
            if (j < w[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);

    cout << dp[n][weight] << endl;
}

优化后：

#include<iostream>

using namespace std;
//一维解法

const int N = 1010;
int dp[N];
int w[N];
int v[N];

int main() {
    int n, weight;
    scanf("%d%d", &n, &weight);

    for (int i = 1; i <= n; i++)
        scanf("%d%d", &w[i], &v[i]);

    for (int i = 1; i <= n; i++)
        for (int j = weight; j >= w[i]; j--)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

    cout << dp[weight];
}

先遍历物品的解法：

#include<iostream>

using namespace std;
//先遍历物品，再遍历容量

const int N = 1010;
int dp[N][N];
int w[N];
int v[N];

int main() {
    int n, weight;
    scanf("%d%d", &n, &weight);

    for (int i = 1; i <= n; i++)
        scanf("%d%d", &w[i], &v[i]);

    for (int i = 1; i <= weight; i++)
        for (int j = 1; j <= n; j++)
            if (i - w[j] < 0) dp[j][i] = dp[j - 1][i];
            else dp[j][i] = max(dp[j - 1][i], dp[j - 1][i - w[j]] + v[j]);
    cout << dp[n][weight];
}