试题：动态规划

爱吃鬼

小艺酱每天都在吃和睡中浑浑噩噩的度过。可是小肚子是有空间上限v的。小艺酱有n包零食，每包零食占据小肚子空间a_i并会给小艺酱一个甜蜜值b_i。小艺酱想知道自己在小肚子空间上限允许范围内最大能获得的甜蜜值是多少?
在这里插入图片描述

使用c++和动态规划解题：一下为参考

#include <iostream>
#include <string>
#include <sstream>
#include <vector>int solution(const int v, const int n, std::vector<std::vector<std::string>>& vec) {int result{ 0 };std::vector<std::vector<int>> dp;dp.resize(n);for (size_t i = 0; i < n; i++){dp[i].resize(v);}// TODO://遍历行（零食数量）for (size_t i = 0; i < n; i++){int a_i = atoi(vec[i][0].c_str());int b_i = atoi(vec[i][1].c_str());//遍历列（空间上限）for (size_t j = 0; j < v; j++){//仅有一个零食，确定第一行的最大甜蜜值if (i == 0) {if (a_i <= j + 1) {dp[i][j] = a_i;}else {dp[i][j] = 0;}}else {if (a_i <= j + 1){//如果可以放下，有两种可能放或者不放//放，则需要读取数量为i - 1的时候，j + 1 - a_i空间时的甜蜜值，之后再加上最新的甜蜜值//j + 1是因为j代表了空间上限，但是j是0开始的int receive_sweetness = dp[i-1][j + 1 - a_i] + b_i;//不放，就相当于i-1个商零食放j的空间，之前已经计算过int reject_sweetness = dp[i - 1][j];//取最大dp[i][j] = receive_sweetness > reject_sweetness ? receive_sweetness : reject_sweetness;}//新增的零食在当前空间容量上限j下，无法放下else {dp[i][j] = dp[i - 1][j];}}}}return dp[n-1][v-1];
}int main() {int v;int n;std::vector<std::vector<std::string>> vec;std::cin >> v;std::cin >> n;std::string line, token;for (int i = 0; i < n; i++) {std::vector<std::string> s;getline(std::cin >> std::ws, line);std::stringstream tokens(line);while (std::getline(tokens, token, ' ')) {s.push_back((token));}vec.push_back(s);}int result = solution(v, n, vec);std::cout << result << std::endl;return 0;
}