30. 有一个人前来买瓜

目录

题目

Input

Output

思路

C++完整代码（含注释）

题目

军训这么累，当然要吃瓜啦。

有一个小军前来买瓜。

众所周知，YHW水果摊里的西瓜的瓜皮子和瓜粒子都是金粒子做的。小军当然想获得尽可能多的金粒子。

一共有n个瓜，每个瓜有重量w，成熟度v，金粒子数量g。

虽然小军的钱是无限的，但他的电动车载重是有限的，因此他不能买总重量超过W的瓜。

"我开水果摊的，能卖给你生瓜蛋子？ ——YHW

因此，当小军买的瓜的总成熟度小于V时，YHW并不会把瓜卖给他。

具体的：水果摊一共有n个瓜，每个瓜有重量w，成熟度v，金粒子数量g。一共有q次询问，每次询问给出两个值W、V，小军要选取n个瓜的子集，使总重量 Σw≤W,总成熟度Σv≥V，求 Σg
的最大值。

Input

第一行输入两个整数,q(1≤n≤100,1≤q≤100)，代表瓜的数量和询问数量。

接下来n行，每行三个整数，第i行的三个整数为i,vi,gi(1≤wi,vi,gi≤100)，分别代表第i个瓜的重量，成熟度和价值。

接下来q行，输入两个整数,V(1≤W,V≤500)，代表一组询问。

Output

输出一共有q行，每行一个整数，分别代表每组询问的最大金粒子数总和，若无合法的买法则输出-1。

思路

本题使用动态规划的思路解决了一个背包问题。通过存储瓜的重量、成熟度和金粒子数的信息，利用一个二维的dp数组来表示状态，通过递推公式来更新状态，然后根据给定的最大重量和最小成熟度处理每组询问，得到最大金粒子数总和。

步骤如下：

1. 确定dp数组以及下标的含义：

   dp数组是一个二维数组，dp[i][j]表示当前重量为i，成熟度为j时的最大金粒子数总和。

2. 确定递推公式：

   在遍历每个瓜的过程中，对于每个状态dp[j][k]，如果当前状态可以转移到状态dp[j + melons[i].weight][min(k + melons[i].maturity, 500)]（重量加上当前瓜的重量不超过最大重量500），则更新转移后的状态的金粒子数总和为dp[j][k] + melons[i].gold，并取较大的值。

3. dp数组的初始化：

   dp数组初始化为-1，表示无法达到该状态。
   而dp[0][0]被设置为0，表示初始状态。

4. 确定遍历顺序：

   遍历瓜的顺序是从0到n-1，即按照输入的顺序遍历瓜的信息。
   对于每个瓜，利用三个嵌套的循环，从重量和成熟度的最大值开始递减遍历，确保在更新dp数组时，可以利用之前计算好的状态。
   这里的遍历顺序是从后往前遍历，以确保之前的状态不被覆盖。
5. 处理输入输出
   完成动态规划的计算后，开始处理每组询问。读取询问的最大重量W和最小成熟度V，并初始化结果result为-1。
   然后，从重量0到最大重量W，从最小成熟度V到500遍历，将每个状态的最大金粒子数总和与result比较，取较大值。
   最后输出每组询问的最大金粒子数总和result。

该算法的时间复杂度为O(nW500)，其中n为瓜的数量，W为最大重量。

C++完整代码（含注释）

提交乐学记得修改！！有查重

#include    
#include    
#include    
using namespace std;// 定义瓜的结构体
struct melon {int weight;int maturity;int gold;
};int main() {int n, q;cin >> n >> q;vector melons(n);// 读取每个瓜的信息for (int i = 0; i < n; i++) {scanf("%d %d %d", &melons[i].weight, &melons[i].maturity, &melons[i].gold);}// dp数组，表示状态vector> dp(501, vector(501, -1));dp[0][0] = 0;// 动态规划计算for (int i = 0; i < n; i++) {for (int j = 500; j >= 0; j--) {for (int k = 500; k >= 0; k--) {// 如果dp[j][k]为有效状态且加上当前瓜的重量不超过最大重量500if (dp[j][k] >= 0 && j + melons[i].weight <= 500) {// 更新状态，取金粒子数总和的较大值dp[j + melons[i].weight][min(k + melons[i].maturity, 500)] = max(dp[j][k] + melons[i].gold, dp[j + melons[i].weight][min(k + melons[i].maturity, 500)]);}}}}// 处理每组询问while (q--) {int W, V;scanf("%d %d", &W, &V);long long result = -1;// 遍历所有可能的状态，取金粒子数总和的最大值for (int j = 0; j <= W; j++) {for (int k = V; k <= 500; k++) {result = max(result, dp[j][k]);}}// 输出结果cout << result << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！