蓝桥杯——无聊的逗

题目来源：蓝桥杯算法训练

知识点：动态规划，等和子集

问题描述
　　逗志芃在干了很多事情后终于闲下来了，然后就陷入了深深的无聊中。不过他想到了一个游戏来使他更无聊。他拿出n个木棍，然后选出其中一些粘成一根长的，然后再选一些粘成另一个长的，他想知道在两根一样长的情况下长度最长是多少。
输入格式
　　第一行一个数n，表示n个棍子。第二行n个数，每个数表示一根棍子的长度。
输出格式
　　一个数，最大的长度。
　　
样例输入
4
1 2 3 1
样例输出
3
数据规模和约定
　　n<=15

问题分析

本题参考了这位博主的解法，讲得很好，点这里看。

这里使用了“0-1背包”的解法，关于“0-1背包”的内容可以看这里。

另外，关于代码中使用到的accumulate求和可以看这里，max_element最大值可以看这里，vector的用法看这里。

代码

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

int getMaxLength(vector<int> lens) {
	int n = lens.size();
	if(n < 2) return 0;
	
	int sum = accumulate(lens.begin(), lens.end(), 0);
	int maxLen = *max_element(lens.begin(), lens.end());
	int target = sum / 2;
	
	if(maxLen > target) return 0;
	
	vector<vector<int> > dp(n, vector<int>(target+1, 0));
	
	for(int i=0; i<n; i++)
	    dp[i][0] = 0;
 
	for(int j=lens[0]; j<=target; j++)
	    dp[0][j] = lens[0];
	    
	for(int i=1; i<n; i++) {
		for(int j=1; j<=target; j++) {
			if(j < lens[i]) dp[i][j] = dp[i-1][j];
			else dp[i][j] = max(dp[i-1][j], dp[i-1][j-lens[i]] + lens[i]);
		}
	}
	
	return dp[n-1][target] == sum/2 ? sum/2 : 0;
}

int main() {
	int n;
	cin >> n;
	
	vector<int> lens(n);
	for(int i=0; i<n; i++) 
		cin >> lens[i];
	
	// 目的是在后面删除元素时不用恢复删掉的元素
	sort(lens.begin(), lens.end());
	
	int sum = accumulate(lens.begin(), lens.end(), 0);
	
	int i = 0;
	int ans = 0;
	
	// 此时可能ans=0，即dp[n-1][weight]!=sum/2
	if(sum % 2 == 0) ans = getMaxLength(lens);
	
	while(i < lens.size()) {
		sum = accumulate(lens.begin(), lens.end(), 0) - lens[i];
		if(sum % 2 == 0) {
			lens.erase(lens.begin() + i);
			ans = max(getMaxLength(lens), ans);
			i = 0; // 目的是从头开始，有可能在删掉现在的元素后，前面有元素又符合条件了
			continue;
		}
		i++;
	}
	
	cout << ans << endl;
	return 0;
}