超级大力士题目用c++怎么写

超级大力士（Super Strong Guy）通常是指编程中的递归或动态规划问题，其中涉及寻找某种最优解或者最大值。例如经典的“背包问题”就属于这种类型，你可以用 C++ 编写一个解决此类问题的通用框架。这里以动态规划的背包问题为例，假设我们有物品 i 的重量 w[i] 和价值 v[i]，目标是在不超过给定总重量 W 的情况下，选择物品使得总价值最大。

#include <iostream>
#include <vector>

int knapsack(int W, std::vector<int>& w, std::vector<int>& v, int n) {
    // 创建一个二维数组 dp[n+1][W+1]，其中 dp[i][j] 表示前i个物品，总重量不超过j时的最大价值
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1));

    // 填充dp表
    for (int i = 0; i <= n; ++i) { // 遍历所有物品
        for (int j = 0; j <= W; ++j) { // 遍历所有可能的重量范围
            if (i == 0 || j == 0) {
                dp[i][j] = 0; // 如果没有物品或重量为零，价值为0
            } else if (w[i - 1] <= j) {
                // 如果当前物品能装入，则选择包含它的价值和不包含它的价值中的较大者
                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
            } else {
                // 当前物品无法装入，直接采用前一个物品的价值
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n][W]; // 返回背包可以达到的最大价值
}

int main() {
    int W = 50; // 容量限制
    std::vector<int> w = {10, 20, 30}; // 物品重量
    std::vector<int> v = {60, 100, 120}; // 物品价值
    int n = w.size(); // 物品数量

    int max_value = knapsack(W, w, v, n);
    std::cout << "背包内最大价值为: " << max_value << std::endl;

    return 0;
}