C/C++背包问题（1）

#include <bits/stdc++.h>
using namespace std;
struct node
{
	double v, w, dwv;
}
a[101];
bool cmp(node a, node b)
{
	return a.dwv > b.dwv;
}
int main()
{
	int n;
	double jg = 0, room;
	cin >> n >> room;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i].v >> a[i].w;
		a[i].dwv = a[i].w * 1.0 / a[i].v / 1.0;
	}
	sort(a, a + n, cmp);
	for (int i = 0; i < n && room>0; i++)
	{
		if (room < a[i].v)
		{
			jg += room * a[i].dwv;
			room = 0;
		}
		else
		{
			jg += a[i].w;
			room -= a[i].v;
		}
	}
	cout << fixed << setprecision(2) << jg;
}

2．01 背包问题（ bag01.cpp ）

【问题分析】 由于物品不能分割，那么能不能再按上面的部分背包问题的方式来解决呢？由样例数据可以看出显然不能再按单位重量的价值大小优先的方式来选择物品了。

????????可以看出如果按单位重量的价值大的第三件物品，此时背包里的价值是 150，背包剩余空间为 3，这时它不能装入其它两件物品的任何一件（4>3,5>3），所以这种方案得到的背包最大价值是 150。

????????但若是装入第一和第二件物品（4+5<10），此时背包的价值为 80+100=180>150，所以这种方案更好。

????????这就像背包问题导入的那种方式一样，一个一个的来试么？

????????对于只有 3 件物品，每件物品有装入或不装入，即每个物品有两种选择，那 3 个物品共有 2*2*2=2 3 =8 种选择，对应为（000, 001, 010, 100, 011, 101, 110, 111）。这样我们就可以枚举出所有 8 种可能。

????????但是如果物品个数是 100 个呢？那会有多少种选择呢？

????????2*2*2*…*2=2100 ≈10 30 ，有么多种可能的方案，显然这是无法枚举出来的！！！

????????那怎么办？？？

????????从背包问题的导入中可以看出，当选择不同的物品时，很多情况下是超出背包的容量，有的是两件物品都无法装入背包里，还用去考虑再加一件物品么？显然是不需要的，那怎么处理呢？

????????由于超出背包容量的不需要关注，那要关注哪些呢？……当然是那些不超过背包容量的啦！背包的容量是 W，也就是说我们只需要关注重量不超过 W 的那些物品组合！

????????现在我们变个魔法，由原来只有 1 个背包 W，变成有 W+1 个背包，背包的容量分别为0,1,2,……,W–1,W，每个背包 bag[i]表示当前所装物品容量不超过 i 的最大价值。显然开始的时候这些背包里的价值都是 0。

????????下面就上面的样例数据来看看这些背包的价值变量情况，以 bag[i]表示背包容量为 i 的当前最大价值：

????????(1) 初始状态：

????????(2) 把第一件物品（重量 w[1]=4，价值 v[1]=80）装入背包里：

????????先考虑背包容量为 10 的，由于当前物品为 w[1]= 4，容量要不超过 10，则空余容量只能选择 bag[10-w[1]]～bag[0]的背包，若这样装入背包 10 中，则价值为 bag[10-w[1]]+v[1]=bag[6]+v[1]=0+80，而原来 bag[10]的价值为 0，显然这种装入会比原来获得更大的价值。

????????再考虑背包容量为 9，8，7，6，5，4 的，若装入，则价值为 bag[9-w[1]] + v[1] = bag[5]+v[1]= 0 + 80，也都比原来的 bag[i] = 0 获得更大的价值，所以更好。

????????而对于背包 1，2，3，由于第 1 件物品的超出了它们的容量，所以无法装入，价值然不变，所以就有以下结果。

????????(3) 把第二件物品（重量 w[2] = 5，价值 v[2] = 100）继续装入背包里：

依然先考虑背包容量为 10 的，由于当前物品为 w[2] = 5，容量要不超过 10，则空余容量只能选择原来容量 bag[10-w[2]]～bag[0]的背包，若这样装入背包 10 中，则价值为bag[10-w[2]] + v[2] = bag[5] + 100 = 80 + 100 = 180，而原来 bag[10]的价值为 80，显然这种装入会比原来获得更大的价值，所以 bag[10]的值更改为 180。

????????再考虑背包容量为 9，装入第二件，则价值为 bag[9-w[2]] + v[2] =bag[4] + 100 = 80 + 100 = 180，也都比原来的 bag[9] = 80 获得更大的价值，所以 bag[9]更改为 180。

????????再考虑背包容量为 8，装入第二件，则价值为 bag[8-w[2]] + v[2] = bag[3] + 100 = 0 + 100 = 100，原来的 bag[8] = 80，100 > 80，所以这种方法更好，更改 bag[8]的值为100。

????????同样背包容量为 7、6、5 的值也更改为 100。

????????而对于背包 1，2，3，4，由于第 2 件物品的超出了它们的容量，所以无法装入，价值依然不变，所以就有以下结果。

????????(4) 把第三件物品（重量 w[3] = 7，价值 v[3] = 150）继续装入背包里：

????????依然先考虑背包容量为 10 的，由于当前物品为 w[3] = 7，容量要不超过 10，则空余容量只能选择原来容量 bag[10-w[3]]～bag[0]的背包，若这样装入背包 10 中，则价值为bag[10–w[3]] + v[3] = bag[3] + 150 = 0 + 150 = 150，而原来 bag[10]的价值为 180，显然这种装入不比原来获得更大的价值，所以 bag[10]的值不变。（背包容量为 9 也同样处理）

????????再考虑背包容量为 8，装入第三件，则价值为 bag[8 – w[3]] + v[3] = bag[1] + 150 = 0 + 150 = 150，原来的 bag[8] = 100，150 > 100，所以这种方法更好，更改 bag[8] 的值为 150。（背包容量为 7 也同样处理）

????????而对于背包 1，2，3，4，5，6，由于第 3 件物品超出了它们的容量，所以无法装入，价值依然不变，所以就有以下结果。

????????这样三件物品装入背包的所有方案已经结束，最后背包容量不超过 10 可以获得的最大价值就是 bag[10] = 180。

????????回头再来想想刚才处理的方法：

????????(1)首先开一个有 W+1 个元素的数组表示 0～W 容量背包所能获得的最大价值，并初始化为 0。

????????(2)依次用把每一件物品装入不同容量的背包中，若当前物品重量为 w[i]，价值为 v[i]（i = 1～n），则对于容量为 j（j = w～1，从大到小）的背包有：

????????????????bag[j] = max(bag[j], bag[j – w[i]] + v[i]) （j >= w[i]）

????????????????bag[j] = bag[j] （j < w[i]）

????????(3)最终答案就是 bag[w]。

#include <bits/stdc++.h>
using namespace std;
int v[1001], w[1001], bag[1001];
int main()
{
	int n, weight;
	cin >> n >> weight;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];
	for (int i = 1; i <= n; i++)
		for (int j = weight; j >= w[i]; j--)
			bag[j] = max(bag[j], bag[j - w[i]] + v[i]);
	cout << bag[weight] << endl;
	return 0;
}

3. 数字组合( num.cpp )

【问题描述】 有 n 个正整数，找出其中和为 t（t 也是正整数）的可能的组合方式。如：

????????N = 5，5 个数分别为 1, 2, 3, 4, 5，t = 5；那么可能的组合有 5 = 1 + 4 和 5 = 2 + 3 和 5 = 5 三种组合方式。

【输入样式】 输入的第一行是两个正整数 n 和 t，用空格隔开，其中（1 ≤ n ≤ 100），表示正整数的个数，t 为要求的和（1 ≤ t ≤ 1000）。

接下来的一行是 n 个正整数，用空格隔开。

【输出样式】 和为 t 的不同的组合方式的数目，由于答案可能太大，输出模 1000000007 的结果。

【输入样例】

????????5 5

????????1 2 3 4 5

【输出样例】

????????3

【问题分析】 可以把和 t 看成背包容量，这里注意的是要求正好装满背包 t 有多少种方案，与前面的的计算略有区别，前面是求不超过 t 的最大价值。

????????由于这里要求的是正好装满 t，如果要处理第 i 个数，则有

????????bag[t] = bag[t] + bag[t – a[i]] (t >= a[i])

????????比如：bag[5]=bag[3]+bag[2]=2+1=3

????????因为不是求最大价值，而是所有方案数，只要是能达到 t - a[i]的方案都可以通过 + a[i]的方法到达 t，所以 bag[t]的方案数就要增加 bag[t – a[i]]。

????????不过这里要提醒的是 bag[0]表示装满 0 容量背包的方案初始化应该是 1（即什么也不装也是一种方案）而不是 0！！！

#include <bits/stdc++.h>
using namespace std;
int bag[1001], n, t;
void work()
{
	long long x, n, t;
	cin >> n >> t;
	bag[0] = 1;
	for (int i = 0; i < n; i++)
	{
		cin >> x;
		for (int j = t; j >= x; j--)
			bag[j] = (bag[j] + bag[j - x]) % 1000000007;
	}
	cout << bag[t] << endl;
}
int main()
{
	work();
}