1019 01背包问题1

#include<iostream>
#include<vector>
using namespace std;

int func(int weight[], int profit[], int capacity, int n_gem)
{
    vector<vector<int>> dp(n_gem + 1, vector<int>(capacity + 1));
    for(int i=0;i<=n_gem;i++)
    {
        dp[i][0] = 0;
    }
    for(int i=0;i<=capacity;i++)
    {
        dp[0][i] = 0;
    }
    for(int i = 1; i <= n_gem; i++)
    {
        for(int j = 1; j <= capacity; j++)
        {
            // 容量允许，可以装入物品
            if(j >= weight[i-1])
            {
                // 分为两种情况，装入物品和不装入物品
                dp[i][j] = max(profit[i - 1] + dp[i - 1][j - weight[i - 1]], dp[i - 1][j]);
            }
            // 容量不足，不装入该物品
            else
            {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n_gem][capacity];
}

int main() {
    // 测试次数
    int n_test;
    cin>>n_test;
    for(int i=0;i<n_test;i++)
    {
        // 宝石个数
        int n_gem;
        cin>>n_gem;
        // 背包容量
        int bag_capacity;
        cin>>bag_capacity;
        int weight[n_gem];
        int profit[n_gem];
        for(int i=0;i<n_gem;i++)
        {
            // 宝石大小
            int weight_gem;
            cin>>weight_gem;
            // 宝石价值
            int profit_gem;
            cin>>profit_gem;
            weight[i] = weight_gem;
            profit[i] = profit_gem;
        }
        cout<<func(weight, profit, bag_capacity, n_gem)<<endl;
    }
   return 0;
}