TopCoder SRM 397 Level2 1000
http://www.topcoder.com/stat?c=problem_statement&pm=8746
一个彩球集合，重量各不相同，给定容器大小如何带回尽量多的彩球
限制条件中彩球个数小于13
因此用DP来计算复杂度为2^13*20*10是可以接受的
这一题用memo方法更加合适因为会有大量的数据不需要计算
每一次都迭代计算所有未填的球
把球放进口袋或者直接开始填下一袋
DP三个参数是mask，剩余袋数和本袋剩余空间
1
import java.util.*;
2import java.util.regex.*;
3import java.text.*;
4import java.math.*;
5import java.awt.geom.*;
6
7public class CollectingMarbles
8
{
9
int[][][] dic;
10 int L;
11 int[] mw;
12 int bagNumber;
13 int cap;
14
15 public int mostMarbles(int[] marblesWeights, int bagCapacity, int numberOfBags)
16
{
17 L = marblesWeights.length;
18 mw = marblesWeights;
19 bagNumber = numberOfBags;
20 cap = bagCapacity;
21 dic = new int[1<<L][bagNumber+1][cap+1];
22 for(int[][] a : dic)
23 for(int[] b : a)
24 Arrays.fill(b, -1);
25 int ans = recur(0, bagNumber, cap);
26 return ans == -1? 0 : ans;
27
}
28
29 private int recur(int mask, int bagNumber, int cur) {
30 // TODO Auto-generated method stub
31 if(bagNumber == 0)
32 return 0;
33 if(dic[mask][bagNumber][cur] > -1)
34 return dic[mask][bagNumber][cur];
35 dic[mask][bagNumber][cur] = 0;
36 for(int i = 0 ; i < L ; ++ i){
37 if((mask & (1 << i)) == 0 && mw[i] <= cur){
38 dic[mask][bagNumber][cur] = Math.max(dic[mask][bagNumber][cur],
39 1+recur(mask|1<<i, bagNumber, cur-mw[i]));
40
41 }
42 dic[mask][bagNumber][cur] = Math.max(dic[mask][bagNumber][cur],
43 recur(mask, bagNumber-1, cap));
44 }
45
46 return dic[mask][bagNumber][cur];
47 }
48
}