C++

$\color{#cc33ff}{— > 算法基础课题解}$

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

dp

                                    闫氏dp分析法

                    集合  从前i个物品中选，总体积<= j的物品的最大价值
        状态表示    
                    属性  最大价值max

dp

        状态计算    集合的划分  选或不选 f[i][j]
                    不选：f[i][j] = f[i-1][j]
                    选：f[i][j] = f[i - 1][j - v] + w

$分析：$

无优化版：

/*

f[i][j] 表示只看前i个物品，总体积是j的情况下，总价值最大是多少。

result = max(f[n][0~v])

f[i][j] :

1、不选第i个物品，f[i][j] = f[i - 1][j]
2、选第i个物品，f[i][j] = f[i - 1][j - v[i]]

f[i][j] = max{1, 2, ···}

f[0][0] = 0

*/

#include<iostream>
#include<algorithm>

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 ++){
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }

    cout << f[n][m];        
    return 0;
}

优化版：

$code1:$

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

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

    cout << f[m];        
    return 0;
}

$code2:$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i ++) {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j --)
            f[j] = max(f[j], f[j - v] + w);
    }

    cout << f[m];

    return 0;
}