学习总结
这周学习了分组的背包问题和二分法；
分组的背包问题就是把n件物品分成若干组，对每组物品至多取一件物品放进背包，在不超过背包容量的情况下，可以存放的最大价值；
状态转移方程：f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]}
注：其中for v的逆排序必须放在for i属于组k之外保证每个组只能有一个被添加到背包；
题目描述：
有 N 组物品和一个容量是 C 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的重量是 w[i][j]，价值是 v[i][j]，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。

#include<iostream>
#include<algorithm>

using namespace std;

int v[100][100] = { 0 };//价值
int w[100][100] = { 0 };//重量
int f[100] = { 0 };

int main()
{
	int N, C;
	int n[100] = { 0 };
	cout << "请输入物品组数和背包容量：" << endl;
	cin >> N >> C;
	for (int i = 1; i <= N; i++)
	{
		cout << "请输入第" << i << "组包含的物品数量：" << endl;
		cin >> n[i];
		for (int j = 1; j <= n[i]; j++)
		{
			cout << "请输入第" << i << "组,第" << j << "个物体的重量和价值：" << endl;
			cin >> w[i][j] >> v[i][j];
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = C; j > 0; --j)
		{
			for (int k = 1; k <= n[i]; k++)
			{
				if (j < w[i][k])
					f[j] = f[j];
				else
					f[j] = max(f[j], f[j - w[i][k]] + v[i][k]);
			}
		}
	}
	cout << f[C] << endl;
	return 0;
}

二分法；
二分法在高中数学中接触过；
定义：在一个单调有序的集合中查找元素，每次将集合分为左右两部分，判断解在哪个部分中并调整集合上下界，重复直到找到目标元素。

while(high - low > 1.0e-6)
{
	 mid = (high + low)/2;
    if(Caculate(mid)<x)
        low=mid;
    else
        high=mid;
}

注：二分查找一定要用单调有序的集合；
小技巧
1，求面积的时候，对于有小数的一般乘以一个较大的数以提高精确度
2，对Π最精确的写法

pi=acos（-1）

心得体会
acm快结课，但我觉得自己对acm的水平一直处于垫底的水平，看着身边的同学飞快的进步，我在反思自己的问题，是自己对课程投入的太少了，对简单的题很容易理解，但稍微加上点难度就很难去想明白它，每种问题的原理都很容易理解，但做题的时候方方面面就都很难能考虑到，还有就是打codeforce的时候，看到其他人都做出两道三道题自己还有半个小时却一道题还没有做出来，心里并不好受，但是这也让我学到了许多，就是想彻底弄明白一道题的体会，就是他是怎么ac的，这么写的原理是什么，上了大学后就大部分知识都是背的，很少有时候真正去钻研一道题，特别是明白了一道题的成就感真的特别好。