华为OD机试 最大花费金额

题目描述

双十一众多商品进行打折销售,小明想购买自己心仪的一些物品,但由于受购买资金限制,所以他决定从众多心仪商品中购买三件,而且想尽可能的花完资金现在请你设计一个程序帮助小明计算尽可能花费的最大资金数额

输入描述

输入第一行为一维整型数组M,数组长度Q小于100,数组元素记录单个商品的价格,单个商品价格小于1000。

输入第二行为购买资金的额度R,R小于100000。

输入格式是正确的,无需考虑格式错误的情况。

输出描述

输出为满足上述条件的最大花费额度

如果不存在满足上述条件的商品,请返回-1。

用例1

输入

23,26,36,27

78

输出

76

说明

金额23、26和27相加得到76,而且最接近且小于输入金额78。

用例2

输入

10,2,3,4,5,6,7,30

20

输出

20

(三指针?)纯暴力,通过70%,凭借回忆复写出来并优化了下

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v;
    int tmp = 0;
    while (cin >> tmp) {
        v.push_back(tmp);
        if (cin.get() == '\n')
            break;
    }
    sort(v.begin(), v.end());
    int l;
    cin >> l;  
    if (v.size() < 3)
        return -1;
    if (v[0] + v[1] + v[2] > l) 
        return -1;
    if (v[0] + v[1] + v[2] == l) {
        cout << l;
        return 0;
    }
    int mx = v[0] + v[1] + v[2];
    for (int i = 1; i < v.size()-1; i++) {//从1开始遍历
        for (int j = 0; j < i; j++) {//左指针
            for (int k = i + 1; j < v.size(); j++) {//右指针
                if(v[i] + v[j] + v[k] == l) {
                    cout << l;
                    return 0;
                }
                else if (v[i] + v[j] + v[k] > l) 
                    break;
                else 
                    mx = max(mx, v[i] + v[j] + v[k]);
            }
            
        }
    }
    cout <<mx;
}

01背包滚动数组解法 自己举了个别用例没通过 没找到是哪里的问题

int main() {
	int tmp = 0,mx=0;
	vector<int>v;
	while (cin >> tmp) {
		v.push_back(tmp);
		if (cin.get() == '\n')
			break;
	}
	sort(v.begin(), v.end());
	cin >> mx;
	vector<int>dp(mx + 1, 0);
	for (int i = v[0]; i <= mx; i++) {
		dp[i] = v[0];
	}
	for (int i = 0; i < v.size(); i++) {
		for (int j = mx; j >=v[i]; j--) {
			dp[j] = max(dp[j - v[i]] + v[i], dp[j]);
		}
	}
	cout << dp[mx];
}

全部评论
01背包问题
点赞 回复 分享
发布于 2023-09-28 02:02 广东

相关推荐

不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
05-12 17:00
门头沟学院 Java
king122:你的项目描述至少要分点呀,要实习的话,你的描述可以使用什么技术,实现了什么难点,达成了哪些数字指标,这个数字指标尽量是真实的,这样面试应该会多很多,就这样自己包装一下,包装不好可以找我,我有几个大厂最近做过的实习项目也可以包装一下
点赞 评论 收藏
分享
但听说转正率很低,我现在有在实习了,好纠结要不要去
熬夜脱发码农:转正率低归低,但是实习的经历你可以拿着,又不是说秋招不准备了
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务