Question

java 数字相加组合

给定一个MAP，例如：
HashMap<String,Integer> hashmap = new HashMap<String,Integer>();
hashmap.put("Item0",1);
hashmap.put("Item1",5);
hashmap.put("Item2",6);
hashmap.put("Item3",2);
hashmap.put("Item4",3);
hashmap.put("Item5",5);
hashmap.put("Item6",1);
hashmap.put("Item7",6);
hashmap.put("Item8",8);
hashmap.put("Item9",8);
KEY是标识，VALUE是数字，
从给定MAP中取VALUE相加，求得相加和小于等于20并最接近20的KEY组合
请给一个最优化算法，可能这个MAP中有几百个值。
求大神帮忙解答。
谢谢。

Answer 1

看你是否要求得所有最优组合，比如有多种组合都接近20，是全出输出还是只输出其中一个。

如果只输出一组组合，就比较简单，使用最简单的动态规划就可以求出来。

如果要输出全部组合，就要先求出这个最优值，然后再进行一次搜索，把所有组合输出。

追问

只要一组就可以，规则是如果等于20，取一组，如果没有等于20，则取最接近的。

追答

ok，那就简单了。
我就着重说一下算法思路，这其实是 【重量=价值】 的 【背包问题】：
建立2个数组，一个是字符串数组s[20]，一个是boolean数组b[20]，长度有20就可以了。
数组初始化s[0]=""; b[0]=true,其余为false
然后就可以对hashmap 进行for循环
对于每一个其中的item，其数值是value,进行i=0~20的循环
如果b[i]==true且i+value<=20且b[i+value]==false时，b[i+value]=true, s[i+value]=s[i]+item;

最后进行进行i=20~0的循环
如果b[i]=true,输出i，输出s[i]，中断循环