【备战秋招】每日一题:2023.3.7-机试(第四题)-塔子哥买商品

news/2024/7/20 16:57:27 标签: 算法, 华为od, python, java, 开发语言

为了更好的阅读体检，可以查看我的算法学习网
在线评测链接:P1069

题目内容

塔子哥是一名工薪族，每个月工资刚刚够支付日常开支，因此他总是需要在超市购买实惠的商品。

有一天，他进入了一家超市，发现超市正在举行一场特殊活动。当塔子哥花费原价买了一件商品时，他可以用半价买下一件右边相邻的商品(也可以用原价购买，这样该商品右边的商品就有次享受半价的机会)。但如果塔子哥半价购买了一件商品，那么下一件右边相邻的商品只能原价购买。

塔子哥有一定的存款，但是他想尽可能多地购买他喜欢的商品，因此他想知道在限制总价不超过 x x x 的情况下，他最多可以获得多少喜爱度。

超市中有 n n n 个商品，每个商品的价格为偶数，第 i i i 个商品的价格为 a i a_i ai​ ，塔子哥对它的喜爱度为 b i b_i bi​ 。

现在，他想要买的商品的喜爱度总和尽可能大，但总价格不能超过 x x x 。你能帮帮他计算最大的喜爱度总和吗？

输入描述

第一行输入两个正整数 n n n 和 x x x ，分别代表商品的数量，以及塔子哥初始的金额数。

第二行输入 n n n 个正整数 a i a_i ai​ ，分别代表每个商品的价格。

第三行输入 n n n 个正整数 b i b_i bi​ ，分别代表每个商品可以给塔子哥带来的喜爱度。

1 ≤ n , x , a i ≤ 1000 1\le n,x,a_i\le 1000 1≤n,x,ai​≤1000

1 ≤ b i ≤ 1 0 9 1\le b_i \le 10^9 1≤bi​≤109
保证所有的 a i a_i ai​ 都是偶数。

输出描述

一个整数，代表最终喜爱度之和的最大值。

样例

输入

5 10
2 2 6 8 4
2 1 4 9 3

输出

13

样例2

输入

3 3
4 10 6
2 1 5

输出

0

解释

钱不够，无法购买任何物品。

思路:动态规划

动态规划，三维dp， d p [ i ] [ j ] [ 0 ] dp[i][j][0] dp[i][j][0] 代表在考虑前 i i i 个商品的基础上，总共花费了 j j j 元时能得到的最大的喜爱度， d p [ i ] [ j ] [ 1 ] dp[i][j][1] dp[i][j][1] 代表相同条件的基础上第 i i i 个商品

用原价购买时的最大喜爱度。

d p [ i ] [ j ] [ 0 ] = m a x ( d p [ i − 1 ] [ j − a [ i ] ] [ 0 ] + b [ i ] , d p [ i − 1 ] [ j − a [ i ] ] [ 1 ] + b [ i ] ) dp[i][j][0] = max(dp[i-1][j-a[i]][0] + b[i], dp[i-1][j-a[i]][1] + b[i]) dp[i][j][0]=max(dp[i−1][j−a[i]][0]+b[i],dp[i−1][j−a[i]][1]+b[i])

d p [ i ] [ j ] [ 1 ] = m a x ( d p [ i ] [ j ] [ 0 ] , d p [ i − 1 ] [ j − a [ i ] / 2 ] [ 0 ] + b [ i ] , d p [ i − 1 ] [ j ] [ 1 ] ) dp[i][j][1] = max(dp[i][j][0], dp[i-1][j-a[i]/2][0] + b[i], dp[i-1][j][1]) dp[i][j][1]=max(dp[i][j][0],dp[i−1][j−a[i]/2][0]+b[i],dp[i−1][j][1])

在dp更新过程中得到最大值即可

类似题目推荐

CodeFun2000

P1025 2022.11.9-攻城战

P1082 2023.3.15-第一题-满二叉树计数

P1069 2023.3.7-第四题:塔子哥买商品

P1081 2023.3.13-第三题-树上同色连通块

代码

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
long long a[N], b[N];
long long dp[N][N][2];
int in() {
	int x;
	cin >> x;
	return x;
}
int main() {
    int n = in(), x = in();
    for (int i = 1; i <= n; i++) {
        a[i] = in();
    }
    for (int i = 1; i <= n; i++) {
        b[i] = in();
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = x; j >= a[i]; j--) {
            if (dp[i - 1][j - a[i]][0] != 0)
                dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - a[i]][0] + b[i]);
            if (dp[i - 1][j - a[i]][1] != 0)
                dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - a[i]][1] + b[i]);
            ans = max(ans, dp[i][j][0]);
        }
        for (int j = x; j >= a[i] / 2; j--) {
            if (dp[i - 1][j - a[i] / 2][0] != 0)
                dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - a[i] / 2][0] + b[i]);
            ans = max(ans, dp[i][j][1]);
        }
        for (int j = 0; j <= x; j++) {
            dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][0]);
            dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][1]);
        }
        if (a[i] <= x) {
            dp[i][a[i]][0] = max(dp[i][a[i]][0], b[i]);
            ans = max(ans, dp[i][a[i]][0]);
        }
    }
    cout << ans << endl;
}

python_143">python

python">if __name__ == '__main__':
	n, x = map(int, input().split())
	a = [0] + list(map(int, input().split()))
	b = [0] + list(map(int, input().split()))
	dp = [ [ [0,0] for i in range(x+1)] for i in range(n+1)]
	ans = 0
	for i in range(1, n+1) :
		if a[i] <= x:	
			dp[i][a[i]][0] = b[i]
			ans = max(ans, b[i])
		for j in range(a[i] ,x+1):
			for k in range(0, 2):
				t = dp[i-1][j - a[i]][k]
				if t == 0:
					continue
				dp[i][j][0] = max(dp[i][j][0], t + b[i])
				ans = max(ans, dp[i][j][0])
		for j in range(a[i] //2 ,x+1):
			t = dp[i-1][j - a[i] // 2][0]
			if t == 0:
				continue
			dp[i][j][1] = max(dp[i][j][1], t + b[i])
			ans = max(ans, dp[i][j][1])
		for j in range(x+1):
			dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][1], dp[i-1][j][0])
	print(ans)

Java

java">import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), x = in.nextInt();
        int[] a = new int[n+1], b = new int[n+1];
        for (int i = 1 ; i <= n ; i ++) {
            a[i] = in.nextInt();
        }
        for (int i = 1 ; i <= n ; i ++) {
            b[i] = in.nextInt();
        }
        long[][][] dp = new long[n+1][x+1][2];
        long ans = 0;
        for(int i = 1 ; i <= n ; i ++) {
            for(int j = x ; j >= a[i] ; j --) {
                if(dp[i-1][j-a[i]][0] != 0)
                    dp[i][j][0] = Math.max(dp[i][j][0], dp[i-1][j-a[i]][0] + b[i]);
                if(dp[i-1][j-a[i]][1] != 0)
                    dp[i][j][0] = Math.max(dp[i][j][0], dp[i-1][j-a[i]][1] + b[i]);
                ans = Math.max(ans, dp[i][j][0]);
            }
            for(int j = x ; j >= a[i]/2 ; j --) {
                if(dp[i-1][j-a[i]/2][0] != 0)
                    dp[i][j][1] = Math.max(dp[i][j][1], dp[i-1][j-a[i]/2][0] + b[i]);
                ans = Math.max(ans, dp[i][j][1]);
            }
            for(int j = 0 ; j <= x ; j ++) {
            	dp[i][j][1] = Math.max(dp[i][j][1], dp[i-1][j][0]);
            	dp[i][j][1] = Math.max(dp[i][j][1], dp[i-1][j][1]);
            }
            if(a[i] <= x) {
                dp[i][a[i]][0] = Math.max(dp[i][a[i]][0], b[i]);
                ans = Math.max(ans, dp[i][a[i]][0]);
            }
        }
        System.out.println(ans);
    }
}

Go

package main

import (
	"fmt"
)

func main() {
	var n, x int
	fmt.Scan(&n, &x)

	a := make([]int, n+1)
	b := make([]int, n+1)
	for i := 1; i <= n; i++ {
		fmt.Scan(&a[i])
	}

	for i := 1; i <= n; i++ {
		fmt.Scan(&b[i])
	}

	dp := make([][][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([][]int, x+1)
		for j := 0; j <= x; j++ {
			dp[i][j] = make([]int, 2)
		}
	}

	ans := 0
	for i := 1; i <= n; i++ {
		for j := x; j >= a[i]; j-- {
			if dp[i-1][j-a[i]][0] != 0 {
				dp[i][j][0] = max(dp[i][j][0], dp[i-1][j-a[i]][0]+b[i])
			}
			if dp[i-1][j-a[i]][1] != 0 {
				dp[i][j][0] = max(dp[i][j][0], dp[i-1][j-a[i]][1]+b[i])
			}
			ans = max(ans, dp[i][j][0])
		}
		for j := x; j >= a[i]/2; j-- {
			if dp[i-1][j-a[i]/2][0] != 0 {
				dp[i][j][1] = max(dp[i][j][1], dp[i-1][j-a[i]/2][0]+b[i])
			}
			ans = max(ans, dp[i][j][1])
		}
		for j := 0; j <= x; j++ {
			dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][0])
			dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][1])
		}
		if a[i] <= x {
			dp[i][a[i]][0] = max(dp[i][a[i]][0], b[i])
			ans = max(ans, dp[i][a[i]][0])
		}
	}

	fmt.Println(ans)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Js

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let input = '';
let currentLine = 0;

process.stdin.on('data', function (data) {
    input += data;
});

process.stdin.on('end', function () {
    input = input.trim().split('\n');
    const [n, x] = input[currentLine++].split(' ').map(Number);
    const a = [0, ...input[currentLine++].split(' ').map(Number)];
    const b = [0, ...input[currentLine++].split(' ').map(Number)];

    const dp = [];
    for (let i = 0; i <= 1005; i++) {
        dp.push([]);
        for (let j = 0; j <= 1005; j++) {
            dp[i].push([0, 0]);
        }
    }

    let ans = 0;
    for (let i = 1; i <= n; i++) {
        for (let j = x; j >= a[i]; j--) {
            if (dp[i - 1][j - a[i]][0] !== 0)
                dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][j - a[i]][0] + b[i]);
            if (dp[i - 1][j - a[i]][1] !== 0)
                dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][j - a[i]][1] + b[i]);
            ans = Math.max(ans, dp[i][j][0]);
        }
        for (let j = x; j >=parseInt(a[i] / 2); j--) {
            if (dp[i - 1][j - parseInt(a[i] / 2)][0] !== 0)
                dp[i][j][1] = Math.max(dp[i][j][1], dp[i - 1][j - parseInt(a[i] / 2)][0] + b[i]);
            ans = Math.max(ans, dp[i][j][1]);
        }
        for (let j = 0; j <= x; j++) {
            dp[i][j][1] = Math.max(dp[i][j][1], dp[i - 1][j][0]);
            dp[i][j][1] = Math.max(dp[i][j][1], dp[i - 1][j][1]);
        }
        if (a[i] <= x) {
            dp[i][a[i]][0] = Math.max(dp[i][a[i]][0], b[i]);
            ans = Math.max(ans, dp[i][a[i]][0]);
        }
    }
    console.log(ans);
});

题目内容均收集自互联网，如如若此项内容侵犯了原著者的合法权益，可联系我: (CSDN网站注册用户名: 塔子哥学算法) 进行删除。


http://www.niftyadmin.cn/n/1250186.html

相关文章

Pytho数据结构与算法8

Pytho数据结构与算法8

目录 1.桶排序 2.计数排序 3.基数排序 4.区别 1.桶排序 桶排序是设计一定数值范围的桶&#xff0c;将属于这个范围的数值放在桶中&#xff0c;然后将元素在每个桶中排序&#xff0c;再按照桶的顺序输出桶中的排序。 def tong_sort(nums):start min(nums)end max(nums)to…
阅读更多...
数据分析11

数据分析11

1.处理911数据 #911数据中不同月份不同类型的电话的次数的变化情况 import pandas as pd import numpy as np from matplotlib import pyplot as plt#把时间字符串转为时间类型设置为索引 df pd.read_csv("./911.csv") df["timeStamp"] pd.to_datetime…
阅读更多...
8个技巧让设计师和程序员好好沟通起来

8个技巧让设计师和程序员好好沟通起来

【优秀外文翻译 第54弹】设计师和程序员在构建产品时扮演着截然不同的角色。设计师通常专注于图形和界面功能&#xff0c;比如菜单布局和配色方案。程序员负责处理能让产品运作的“幕后”工作&#xff0c;通常涉及代码。所以&#xff0c;设计师和程序员之间存在断层也正常。有时…
阅读更多...
Python数据结构与算法9

Python数据结构与算法9

1.栈&#xff1a;一种数据集合&#xff0c;可以理解为只能在一段进行插入或删除操作的列表 特点&#xff1a;后进先出 代码实现栈&#xff1a; class Stack:def __init__(self):self.stack[]def push(self,element): #进栈self.stack.append(element)def pop(self):return …
阅读更多...
设计的工程化,来自Codesigner程序员X设计师的分享

设计的工程化,来自Codesigner程序员X设计师的分享

这篇文章是社区成员ML404 Jun在 Mixlab 广州线下分享活动内容的总结&#xff0c;Jun是一名喜欢设计和代码的互联网从业者&#xff0c;兴趣广泛&#xff0c;从设计到代码均有涉猎&#xff0c;目前专注于设计系统和工具的探索。他做过的东西如下&#xff1a;- 公众号&#xff1a;…
阅读更多...
下一代搜索引擎？我们需要技术、设计、场景的无界思考

下一代搜索引擎？我们需要技术、设计、场景的无界思考

头条进军搜索&#xff0c;pk的是百度搜索吗&#xff1f;还是另有所图&#xff1f;更有文章评论为「下一代搜索引擎」。今天我们以技术VS设计的角度&#xff0c;来聊聊「下一代搜索引擎」 。搜索引擎帮助我们寻找到互联网上散落在各处的信息&#xff1b;移动互联网兴起之后&…
阅读更多...
Python数据结构与算法10

Python数据结构与算法10

目录 链表 定义 创建 遍历 插入 删除 双链表 插入 删除 总结 链表 定义 由一系列节点组成的元素集合。每个节点包括两部分&#xff0c;数据域和指向下一个节点的指针 创建 头部法 class Node:def __init__(self,item):self.itemitemself.nextNone def create_linklist_h…
阅读更多...
数据结构11

数据结构11

1.假设单链表L(a1,b1,a2,b2,---,an,bn)&#xff0c;设计算法实现L1(a1,a2,---,an) L2(bn,bn-1,----b1) void split(LinkNode*& L, LinkNode*& L1, LinkNode*& L2) {LinkNode* p L->next, * q, * r1;L1 L;r1 L1;L2 (LinkNode*) malloc(sizeof(LinkNode));…
阅读更多...
最新文章

Copyright @ 2022~2023