华为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];
}