题目描述：

 

新学期伊始，适逢顿顿书城有购书满  x 元包邮的活动，小 P 同学欣然前往准备买些参考书。
一番浏览后，小 P 初步筛选出 n 本书加入购物车中，其中第 i 本（1≤ i ≤ n）的价格为 a[i] 元。
考虑到预算有限，在最终付款前小 P 决定再从购物车中删去几本书（也可以不删），使得剩余图书的价格总和 sum 在满足包邮条件（sum ≥ x）的前提下最小。

试帮助小 P 计算，最终选购哪些书可以在凑够 x 元包邮的前提下花费最小？

输入格式：

从标准输入读入数据。

输入的第一行包含空格分隔的两个正整数 n 和 x ，分别表示购物车中图书数量和包邮条件。

接下来输入 n 行，其中第 i 行（1≤ i ≤ n）仅包含一个正整数 a[i]，表示购物车中第 i 本书的价格。输入数据保证 n 本书的价格总和不小于 x 。

输出格式：

输出到标准输出。

仅输出一个正整数，表示在满足包邮条件下的最小花费。

示例：

4 100
20
90
60
60

样例1输出：

110

        说明：最小花费为：90+20 = 110。

 题目阅读思路：

        若不了解背包问题有关知识，首先想到的应该是递归深度优先枚举遍历，再剪枝的办法。

        即：将书本价格从大到小排序，然后通过递归的办法逐一枚举。

递归代码示例：

/*递归剪枝*/
int func(int number[],int &min,int pre,int all,int n,int I) {
	int temp = 0;
	for (int i = I; i < n; i++) {
		temp = pre + number[i];
		cout << "i=" << i<<' '<<"temp="<<temp<<endl;
		if (temp >= all) {
			if (min > temp) min = temp;
			continue;
		}
		min = func(number, min, temp,all,n,i+1);
	}
	return min;
}
int main() {
	int n;
	int all;
	cin >> n >> all;
	int number[33];
	int sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> number[i];
		sum += number[i];
	}
	int min = 9999;
	sort(number,number+n);
	func(number,min,0,all,n,0);
	return min;
}

显然这种暴力枚举的策略并非本题正解。

01背包问题：

在解释本题正解之前，应当先了解一些背包问题的知识。当然如果你已经知道了，也就应该做出来了，能看到这的应该都是不知道背包问题的。

so背包问题：

        有一个容量为 n 的背包，以及 m 个价值各异的物品，当然它们都有体积。

        第 i 个物品的价值记为：value[i]。体积记为：volume[i]。

        问：这个背包能装入最大的价值为多少？

（当然聪明的同学应该已经联想到背包问题与书本包邮问题有多么类似，只需稍加转换就是同一个问题）

那么像这样的背包问题应该如何解决呢？

答案就是动态规划！ 没错背包问题也是动态规划问题的一种，但是递推表达式非常非常隐蔽。

若对动态规划问题不熟悉的同学也不必焦虑，动态规划只是个看起来很高大上的名词，斐波那契数列的题目做过没？这就是个动态规划问题。即通过子问题求解主问题，通过递推关系式而不是从头计算从而节省时间和空间。若还不明白则可以进博主空间搜“动态规划”进行几个小问题的学习我相信你就已经完全明白动态规划是个什么样的东西了。

到此为止，小博主就默认各位看官有动态规划的基础知识，那么我相信你们一定知道动态规划问题最重要的就是求解递推关系式，而递推关系式往往隐藏在题目中有限制条件的语句之中。

然而可惜的是，背包问题咋一看并没有明显的限制条件，这也是为什么背包问题在动态规划问题中会如此抽象的原因。

其实切入点在于子问题的求解。

子问题：

若背包容量不变，物品数量减一，减去的那个放在我们手上，该情况下最大价值假设为valuemax[m-1]。

请问，当物品数量不减的时候，即：把我们手上的物品也加入判断的时候，最大价值为多少呢？

显然这需要分情况讨论。

若，手上物品加入背包，背包不会溢出，那么直接放即可

关键是剩下这种情况：若背包会溢出怎么办？

        此时我们有一个打底的价值：valuemax[m-1]。即手上就不放进去，此时价值为valuemax[m-1]

        但我们还有另外一种情形没有考虑：即手上物品放进去，然后取出一些物品来防止溢出，使得价值更高。

精彩的来了同学们。上一句话的情形是不是可以理解为:

有一个背包，容量为: n-volumn[m]，有m-1个物体求该情况下最大价值，并记为valuemax_2;

此时，背包会溢出情况下：valuemax[m] = max{valuemax[n-1] , valuemax_2+value[m] }

同学们可以暂停理解一下，这里比较抽象。

那么我们除了物体的数量这个变量，我们又引入了背包容量这个变量，没错，在背包问题中背包容量也构成一个子问题变量。

由此我们可以创建一个二维数组dp[m][n]---------一共有m个物体，背包容量为n。

        dp[ i ][ j ] 数组存储的是在容量为 j 的背包下，i 个物体往里放的最大价值

显然，当 j==0 时，dp[i][j]==0。

           当 i==0 且容量>volume[1]时，dp[i][j] = value[i][j];

其余格子赋值为0即可。至此，初始化完成。

物品 \ 容量	0	1	2	3	4	5
物品1：体积1	0	value[1]	value[1]	value[1]	value[1]	value[1]
物品2：体积2	0	0	0	0	0	0
物品3：体积3	0	0	0	0	0	0

现在只需，逐个遍历物品和容量，那么具体应该如何给dp数组赋值呢？

如果同学们能理解子问题模块的话，那么写起来简直不要太容易：

	for (int i = 1; i < n; i++) {//物品
		for (int j = 0; j <= sum; j++) {//背包容量
			dp[i][j] = dp[i - 1][j];
			if (volume[i]+dp[i - 1][j]<=j) dp[i][j] = dp[i - 1][j]+value[i];
			else if(j>=volume[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - volume[i]] + value[i]);
			if (dp[i][j] > maxfinal) maxfinal = dp[i][j];
		}
	}

 最终dp数组的样子：

物品 \ 容量	0	1	2	3	4	5
物品1：体积1,价值1	0	value[1]	value[1]	value[1]	value[1]	value[1]
物品2：体积2,价值2	0	value[1]	value[2]	value[1]+ value[2]	value[1]+ value[2]	value[1]+ value[2]
物品3：体积3,价值3	0	value[1]	value[2]	value[3]	value[1]+ value[3]	value[2]+ value[3]

呼，背包问题就此结束。

虽然背包问题看起来就这短短几行代码，但理解起来可难度不小。

由此我们返回到何以包邮问题。

之前有过铺垫，此时同学们应该可以马上回忆起来，何以包邮问题，只需要将所有书籍的价格加起来再减去包邮价格，就是我们所谓的背包问题。

此时，每本书的 value = volume = 价格。只需要在背包问题里改几个变量即可。

话不多说直接上代码

int func(int n,int number[],int sum) {
	vector<vector<int>> dp(n, vector<int>(sum + 1, 0));
	if (number[0] > sum) return 0;
	for (int j = 0; j <= sum; j++) {
		if (j >= number[0])
			dp[0][j] = number[0];
		else dp[0][j] = 0;
		//cout << 0 << ' ' << j << ' ' << dp[0][j] << endl;
	}
	for (int i = 0; i < n; i++) dp[i][0] = 0;
	int maxfinal = 0;
	for (int i = 1; i < n; i++) {//物品
		for (int j = 0; j <= sum; j++) {//背包容量
			dp[i][j] = dp[i - 1][j];
			if (number[i]+dp[i - 1][j]<=j) dp[i][j] = dp[i - 1][j]+number[i];
			else if(j>=number[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - number[i]] + number[i]);
			if (dp[i][j] > maxfinal) maxfinal = dp[i][j];
		}
	}
	return maxfinal;
}
int main() {
	int n;
	int all;
	cin >> n >> all;
	int number[33];
	int sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> number[i];
		sum += number[i];
	}
		
	sort(number,number+n);
	cout<<sum-func(n,number,sum-all);
	return 0;
}

注意：对了，记得先排序。为了保证递推成立，有小到大是必不可少的条件。