问题描述
逗志芃在干了很多事情后终于闲下来了，然后就陷入了深深的无聊中。不过他想到了一个游戏来使他更无聊。他拿出n个木棍，然后选出其中一些粘成一根长的，然后再选一些粘成另一个长的，他想知道在两根一样长的情况下长度最长是多少。
输入格式
第一行一个数n，表示n个棍子。第二行n个数，每个数表示一根棍子的长度。
输出格式
一个数，最大的长度。
样例输入
4
1 2 3 1
样例输出
3
数据规模和约定
n<=15
思路一：
利用算法dp类似01背包的做法，将问题进行一个肢解。
这里用到了一个分割等和子集的思想具体可以参考：
416. 分割等和子集，动态规划之01背包问题，详细解释 - 分割等和子集 - 力扣（LeetCode） (leetcode-cn.com)
但是这里的是用到这个思想，在这思想上做了一点小小的改进。
具体如下：
其他的一些细节都写在代码的注释里面了。
这个题解不完美，没有全部ac，只是强调了分割等和子集的思想。
ac了80还有两个没有ac应该是str数组处理的问题，因为我的str数组里面存了这个数的所有可能性没有单一处理，如果str里面存的是单一的构成这个数据的源位置的话，那么我觉得这个问题应该是可以解决了，如果解决了这个问题，应该ac是没有问题了。
import java.util.*;
public class Mainx6 {
/*
* 为了把函数传参数更方便，代码更简单，直接将这个比较作为了全局变量。
*/
static String[] str;
public static void main(String[] args) {
// TODO 自动生成的方法存根
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
int number = in.nextInt();
int[] arr = new int[number];
int mid = 0;
for(int i=0;i<number;i++) {
arr[i] = in.nextInt();
mid += arr[i];
}
if(mid%2==1)mid-=1;mid = mid/2;//此时的mid是这组数据总和的一半
/*
* 以上都是数据的输入以及为了将数据的数据量进行一个在缩小。
* 我设置了一个mid值，这个值是为了后期的我杀数据量用的。
* mid原理：因为我的数据的值要分作为两组的话，所以总的数据量向下取整就是这个最大的可能结果
* 又因为我们要求的是最大值，所以此时我将这个mid的值进行了一个向下迭代更新，每次更新进行一个相应的判断。
*/
/*
* fuben数组是用来备份原数组的，因为我要在原来的数组里面进行一个数组的修改，以便用来判断剩下的
* 数据是否符合条件。
*/
int[] fuben = new int[number];
for(int i=0;i<number;i++) {
fuben[i] = arr[i];
}
//此时建立一个boolean类型的数组
boolean daan = false;
for(;mid>0;mid--) {
/*
* 将mid值进行一个更新并进行一个循环判断。
* 下面先初始化每一次的bol数组，和存数据组成的string数组
*/
boolean[] bol = new boolean[mid+1];bol[0] = true;
str = new String[mid+1];str[0] = "";
if(Division(bol,arr,str,mid)) {
/*
* 若当前的一个判断成立的话，那么就进行一个继续的判断
* 且将这个能构成的mid的值的源数据进行覆盖掉，以便下一次的循环不会匹配到
*/
// System.out.println(str[mid]);
String temp = str[mid];int tempmid = mid;
char[] tempchar = temp.toCharArray();
for(int i=tempchar.length-1;tempmid!=0;i--) {
if(tempchar[i]>='0'&&tempchar[i]<='9') {
tempmid-=(arr[tempchar[i]-'0']);
arr[tempchar[i]-'0'] = Integer.MAX_VALUE;//重复的太多了，应该是后面的数据处理的地方改一改就可以了
}
}
/*
* 当代码运行到这里以后说明
* 当下已经匹配成功了第一次并且对相应的值进行了一个覆盖
* 此时要对剩下的数据进行一个查找，用以确保是否能再次凑齐mid。
* 若能下面会进行一个标记，也就是daan的一个标记，并且直接结束循环，节省时间。
*/
//另一部分
bol = new boolean[mid+1];bol[0] = true;
str = new String[mid+1];str[0] = "";
if(Division(bol,arr,str,mid)) {
System.out.println(mid);
daan = true;
break;
}
for(int i=0;i<number;i++) {
arr[i] = fuben[i];
}
}
}
//另一部分
if(!daan)System.out.println(0);
}
}
/*
* 这边算是整个代码最为核心的一个部分，这个代码做的事情就是将你给的数组里面和目标值进行一个匹配，最后返回mid那个位置的boolean值。
* 判断里面的值是否能构成这个给定的值，这边采用的dp（分割等和子集的思想）只不过是做了一些相应的一个变化
* boolean[]数组：多开一个位置并初始化将0的位置初始化为TRUE，true表示我当前位置的值可以由数组里面的值进行一个组合
* false则反之。这个方法到时候我会在博客中进行一个相应的介绍，这边只是将这个代码的构建进行一个简单的解释，这边不在赘述。
* arr[]数组：原数据组
* str[]数组：对当前的这个值若为TRUE的话，将用能构成这个值的可能性进行一个写入
*/
static boolean Division(boolean[] bol,int[] arr,String[] str,int mid) {//进行一个判断是否存在这个中间值
for(int i=0;i<arr.length;i++) {
//if(arr[i]<mid)
for(int j=mid;j>=arr[i];j--) {
bol[j] = (bol[j] || bol[j-arr[i]]);
if(bol[j-arr[i]]) {
if(str[j]==null)str[j] = "";
/*
* 将数据的来源进行写入的时候，我觉得这边有必要解释一下。
* 因为我们是判断当前的这个位置的值是否能进行一个由数组里面的值进行一个构成嘛。
* 所以我们利用当前的这个循环的j也就是mid来减去当前循环数据数组的值，判断bol[mid减去当前循环数据数组的当前值]是否为TRUE
* 若为TRUE的话，此时就说明当前的这个j是可以被数组里面的数组进行一个构成的。
*
* 这边我解释一下：这个为什么可以这么判断，因为我们循环判断的是bol数组里面的每一个位置，也就是每一个值，
* 然后又对数据数组进行一个循环，利用这个每一个值减去这个当前的数据数组里面的循环值，因为数据数组里面的值是一定存在的，
* 所以此时我只需要判断当前值减去这个数据数组的循环值这个bol值能否成立（也就是当前的减去以后的这个值能否被数据数组里面的值构成）
* 如此当我的bol数组循环完
* 答案就是我的bol[mid]
*/
str[j] += str[j-arr[i]] +i+',';//重点！！！！
}
}
if(bol[mid])break;
}
return bol[mid];
}
}还有在当时对这题的一些想法一并写在这里。
还有一种思路就是这样的，利用输入进来的数据量比如输入4的话那么这四个数据的分组的可能性有2的4次方种，分别为0001,0010,0011.......等等~
这样的话我只需要对这个2的4次方内的所有数字进行一个十进制转2进制的处理，然后利用>>和<<对当下的这个2进制数据进行一个取值就可以分组了。分组以后再利用我的mid进行一个数据筛选，筛选以后记录最大值。
这种思路的话我觉着麻非常妙。然后只是所有的可能性都要进行一个遍历，这个的话，后面进行遍历的时候处理一下就好了。
好了。溜了溜了
祝各位学业顺利，加油加油！
我所走的每一步，都是为了更接近你。————《艺伎回忆录》