【c++笔试强训】（第二十六篇）

chika和蜜柑（排序/topK）

题目解析

讲解算法原理

编写代码

01背包（动态规划-01背包）

题目解析

讲解算法原理

编写代码

chika和蜜柑（排序/topK）

题目解析

1.题目链接：登录—专业IT笔试面试备考平台_牛客网

2.题目描述

题目描述

chika很喜欢吃蜜柑。每个蜜柑有一定的酸度和甜度，chika喜欢吃甜的，但不喜欢吃酸的。
一共有n个蜜柑，chika吃k个蜜柑，将获得所吃的甜度之和与酸度之和。chika想获得尽可能大的甜度总和。如果有多种方案，她希望总酸度尽可能小。
她想知道，最终的总酸度和总甜度是多少？

输入描述:

第一行有两个正整数n和k，分别代表蜜柑总数和chika吃的蜜柑数量。(1≤k≤n≤200000)
第二行有n个正整数ai，分别代表每个蜜柑的酸度。（1≤ai≤1e9）
第二行有n个正整数bi，分别代表每个蜜柑的甜度。（1≤bi≤1e9）

输出描述:

两个正整数，用空格隔开。分别表示总酸度和总甜度。

示例1

输入

3 2 1 3 4 2 2 5

3 2
1 3 4
2 2 5

输出

5 7

5 7

说明

选择1号和3号蜜柑，总酸度为5，总甜度为7，为最优解。

讲解算法原理

解法：
算法思路：
排序：
将每个橘⼦按照甜度由⾼到低排序，相同甜度的橘⼦按照酸度由低到⾼排序。
然后提取排序后的前k个橘⼦就好了。

编写代码

c++算法代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII; // <酸度，甜度>
PII arr[N];
int n, k;
int main()
{cin >> n >> k;for(int i = 0; i < n; i++) cin >> arr[i].first; for(int i = 0; i < n; i++) cin >> arr[i].second;  sort(arr, arr + n, [&](const PII& a, const PII& b) { if(a.second != b.second) return a.second > b.second; else return a.first < b.first; });long long s = 0, t = 0; for(int i = 0; i < k; i++) { s += arr[i].first; t += arr[i].second; }cout << s << " " << t << endl;return 0;
}

java算法代码：

import java.util.*;
class Orange
{int a; // 酸度int b; // 甜度 Orange(){} Orange(int a, int b){this.a = a;this.b = b;}
}
public class Main
{public static void main(String[] args){Scanner in = new Scanner(System.in); int n = in.nextInt(), k = in.nextInt(); Orange[] o = new Orange[n]; for(int i = 0; i < n; i++){o[i] = new Orange(); o[i].a = in.nextInt(); } for(int i = 0; i < n; i++) { o[i].b = in.nextInt(); }// 排序Arrays.sort(o, (x, y) -> {if(x.b == y.b) return x.a - y.a; return y.b - x.b;});// 提取结果long x = 0, y = 0; for(int i = 0; i < k; i++) { x += o[i].a; y += o[i].b; }System.out.println(x + " " + y);}
}

01背包（动态规划-01背包）

题目解析

1.题目链接：01背包_牛客题霸_牛客网

2.题目描述

描述

已知一个背包最多能容纳体积之和为v的物品

现有 n 个物品，第 i 个物品的体积为 vi , 重量为 wi

求当前背包最多能装多大重量的物品?

数据范围： 1 \le v \le 10001≤v≤1000 ， 1 \le n \le 10001≤n≤1000 ， 1 \le v_i \le 10001≤vi≤1000 ， 1 \le w_i \le 10001≤wi≤1000

进阶：O(n \cdot v)O(n⋅v)

示例1

输入：

10,2,[[1,3],[10,4]]

返回值：

4

说明：

第一个物品的体积为1，重量为3，第二个物品的体积为10，重量为4。只取第二个物品可以达到最优方案，取物重量为4

示例2

输入：

10,2,[[1,3],[9,8]]

返回值：

11

说明：

两个物品体积之和等于背包能装的体积，所以两个物品都取是最优方案

讲解算法原理

解法：
算法思路：
01背包模板题：
1. 状态表⽰：
dp[i][j] 表⽰从前 i 个物品中挑选，总体积不超过 j 的情况下，最⼤重量是多少。
2. 状态转移⽅程：
根据「最后⼀步」的状况，来分情况讨论：
i. 不选第 i 个物品：相当于就是去前 i - 1 个物品中挑选，并且总体积不超过 j 。此
时 dp[i][j] = dp[i - 1][j] ；
ii. 选择第 i 个物品：那么我就只能去前 i - 1 个物品中，挑选总体积不超过 j - v[i]的物品。此时 dp[i][j] = dp[i - 1][j - v[i]] + w[i] 。但是这种状态不⼀定存在，因此需要特判⼀下。
综上，状态转移⽅程为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) 。

编写代码

c++算法代码：

class Solution
{int dp[1010] = { 0 };
public:int knapsack(int V, int n, vector<vector<int> >& vw) {for(int i = 0; i < n; i++){for(int j = V; j >= vw[i][0]; j--){dp[j] = max(dp[j], dp[j - vw[i][0]] + vw[i][1]);}}return dp[V];}
};

java算法代码：

import java.util.*;
public class Solution
{int[] dp = new int[1010]; public int knapsack (int V, int n, int[][] vw)  { for(int i = 0; i < n; i++) { for(int j = V; j >= vw[i][0]; j--) { dp[j] = Math.max(dp[j], dp[j - vw[i][0]] + vw[i][1]); }}return dp[V];}
}