Java 背包算法计算从数组中找若干个数使其最接近某个数

背包的算法的动态方式如下:

f(i,w) = max{ f(i-1,w), f(i-1,v-weight[i])+value[i] }

状态转移方程理解如下：

f(i,w)表示前i个物体面对容量为w时背包的最大价值，weight[i]代表物体i的重量(即重量)，value[i]代表物体i的价值；如果第i个物体不放入背包，则背包的最大价值等于前i-1个物体面对容量v的最大价值；如果第i个物体选择放入，则背包的最大价值等于前i-1个物体对容量w-weight [i]的最大价值加上物体i的价值value[i]。


综上，第i件物品要么选，要么不选。
1）如果不选，则第i件物品放w容量的最优值等于第i-1件物品放w容量的最优值；
2）如果i选，则第i件物品放w-weight容量的最优值再加value[i]的值。

现在我们的问题是：在一个数组中有若个数据，找出最接近所有数据10%的值？而且我们的实际情况是数组中存在的是实数，物品只有三百个左右，而待查找的数是几十万的情况。

做法：
1）所有的数据进行格式化处理，剔除小于100的数，实数四舍五入变正整数；
2）待查找的数降100倍，同时格式化的数据也进行降100倍处理，这样可以大大节省内存空间。

核心代码如下：

public static void beiBao() {
		// 背包的容量大小，最大的数据为50w，10%就是5w，再降100倍，即为500
		int dp[] = new int[501];
		char state[][] = new char[deal_Array.length][501]; /* 记录路径的二维数组 */
		int i, j;
		int M = 49602 / 100; // 待查找近似值
		/* 01背包 */
		for (i = 0; i < deal_Array.length; ++i) {
			for (j = M; j >= deal_Array[i]; --j) {
				int tmp = dp[j - deal_Array[i]] + deal_Array[i];
				if (tmp > dp[j]) {
					dp[j] = tmp;
					state[i][j] = 1;
				}
			}
		}
		i = deal_Array.length; // 第几个商品
		j = M;// 当前背包容量
		System.out.println("============================");
		while ((--i) >= 0) {
			if (state[i][j] == 1) {
				System.out.print(deal_Array[i] + " ");
				j -= deal_Array[i];
			}
		}
}