“求价值最大和”，毋庸置疑，用动态规划。此类题目属于动态规划中的一个特殊类别——“背包问题”。

PS：背包问题可以分为三种——

  1. 0/1背包问题——物品只有选/不选两种状态，求最大价值和
  2. 子集背包问题——分割等和子集问题
  3. 完全背包问题——物品可以无限选，求可以组合成目标值的选法

设当前个数为i，当前最大背包容量为j，那么dp[i][j]表示“背包容量为j时，在前i个物品中选择的最大价值和”。有如下状态公式(设w为重量数组，v为价值数组)：

  1. 如果j-w[i-1]>=0，dp[i][j] = max(dp[i-1][j-w[i-1]]+v[i-1], dp[i-1][j])
  2. 如果j-w[i-1]<0，dp[i][j] = dp[i-1][j]
  3. 基准1: dp[0][..]=0
  4. 基准2: dp[..][0]=0

解释状态公式：

  1. 如果当前背包重量减去当前物品重量后还有余地，那么当前最大价值和为“选当前物品”和“不选当前物品”两种情况的较大值
  2. 如果当前背包重量减去当前物品重量后没有剩余空间了，那么当前最大价值和为“不选当前物品”的最大价值和
  3. 基准1: 在物品数量为0的情况下，最大价值和永远为0
  4. 基准2: 在背包容量为0的情况下，最大价值和也永远为0

代码如下：

//
// Created by jt on 2020/8/26.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> w, v;
    for (int i = 0; i < N; ++i) { int a; cin >> a; w.push_back(a); }
    for (int i = 0; i < N; ++i) { int a; cin >> a; v.push_back(a); }
    vector<vector<int>> dp(N+1, vector<int>(M+1, 0));
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            dp[i][j] = j-w[i-1] >= 0 ? max(dp[i-1][j-w[i-1]]+v[i-1], dp[i-1][j]) : dp[i-1][j];
        }
    }
    cout << dp[N][M] << endl;
}