子集和问题：按给定子集和完全划分集合

柔情只为你懂 2022-02-04 16:09 285阅读 0赞

需求是这样的：  
有44个数字A1-A44：1420, 1198, 493, 300, 3006, 881, 2450, 1372, 3643, 1350, 598, 615, 740, 820, 841, 820, 1025, 885, 270, 270, 270, 270, 270, 1735, 885, 4719, 1661, 1435, 2255, 5895, 6465, 870, 330, 750, 1365, 2085, 3370, 1995, 7990, 381, 2048, 840, 6880, 7723

另有3个数字S1-S3：31827, 37944, 15713

44个数据分成三组，使每一组的和分别等于S1、S2、S3，即第一组的和等于S1，第二组的和等于S2，第三组的和等于S3.。  
44个数据中的每一个数，要么属于第一组，要么属于第二组，要么属于第三组，不能即属于第一组又属于第二组。

结果：37944等于1420,1198,493,300,3006,881,2450,1372,3643,1350,598,615,740,820,841,820,1025,885,270,270,270,270,270,1735,885,4719,1435,870,330,750,1365,2048,
    31827等于
    1661,2255,5895,6465,2085,3370,1995,381,840,6880,
    15713等于
    剩下的

public class test { 
    	static int sum = 0;
    	static int sum2 = 0;
    	static int c = 0;
    	static int c2 = 0;
    	static int n = 0;
    	static int[] arr;
    	static int[] temp;
    	static int[] temp2;
    
    	static int t = 0;
    	static int t2 = 0;
    
    	public static void main(String[] args) { 
    		n = 44;
    		c = 37944;
    		c2 = 31827;
    		temp = new int[n];
    		temp2 = new int[n];
    
    		arr = new int[] {  1420, 1198, 493, 300, 3006, 881, 2450, 1372, 3643, 1350, 598, 615, 740, 820, 841, 820, 1025,
    				885, 270, 270, 270, 270, 270, 1735, 885, 4719, 1661, 1435, 2255, 5895, 6465, 870, 330, 750, 1365, 2085,
    				3370, 1995, 7990, 381, 2048, 840, 6880, 7723 };
    		search(0);
    		if (t == 0) { 
    			System.out.println("No Solution!");
    		}
    	}
    
    	public static void search(int m) { 
    		if (sum == c) { 
    			t = 1;
    			int[] sub = new int[m];
    			for (int i = 0; i < m; i++) { 
    				if (temp[i] == 1) { 
    					sub[i] = arr[i];
    				}
    			}
    			int[] bb = buji(sub);
    			search2(bb, 0);
    			for (int i = 0; i < sub.length; i++) { 
    				if (sub[i] == 0)
    					continue;
    				System.out.print(sub[i] + ",");
    			}
    			return;
    		}
    		if (sum > c || m == n) { 
    			return;
    		}
    		if (sum + arr[m] <= c) { 
    			sum += arr[m];
    			temp[m] = 1;
    			search(m + 1);
    			temp[m] = 0;
    			sum -= arr[m];
    		}
    		search(m + 1);
    	}
    
    	public static void search2(int[] bb, int m2) { 
    		int n = bb.length;
    		if (sum2 == c2) { 
    			t2 = 1;
    			System.out.println("");
    			System.out.println("");
    			for (int i = 0; i < m2; i++) { 
    				if (temp2[i] == 1) { 
    					System.out.print(bb[i] + ",");
    				}
    			}
    			System.out.println("");
    			System.exit(0);
    			return;
    		}
    		if (sum2 > c2 || m2 == n) { 
    			return;
    		}
    		if (sum2 + bb[m2] <= c2) { 
    			sum2 += bb[m2];
    			temp2[m2] = 1;
    			search2(bb, m2 + 1);
    			temp2[m2] = 0;
    			sum2 -= bb[m2];
    		}
    		search2(bb, m2 + 1);
    	}
    
    	// 从求一个集合和子集的补集
    	public static int[] buji(int[] b) { 
    		int[] arr2 = new int[n];
    		arr2 = arr;
    		for (int i = 0; i < b.length; i++) { 
    			for (int j = 0; j < arr2.length; j++) { 
    				if (b[i] == arr2[j]) { 
    					arr2[j] = 0;
    					break;
    				}
    			}
    		}
    		int k = arr.length - b.length;
    		int[] cc = new int[k];
    		for (int i = 0, j = 0; i < arr2.length; i++) { 
    			if (arr2[i] == 0) { 
    				continue;
    			}
    			if (j < k) { 
    				cc[j] = arr2[i];
    				j++;
    			}
    		}
    		return cc;
    
    	}
    }