背包问题；author：tc；

发表于

ohohoh！这是tc的第一篇博客呢。nice
这回是背包，自己感觉总是忘记然后就哎，说多了都是泪。ok。
背包问题最主要的是状态转移方程。讲道理就最主要的是选和不选的问题。然后我个人觉得它就是优化版的贪心问题，其实他的状态转移方程就基本是贪心的思想。

0/1 背包。

这个是题大概就是每个物品只有一件，然后每个物品有他的价值和占用空间，然后就求最多价值可以试多少。
题目：0/1背包
这是他的状态转移方程
f[n] = max(f[n - w[i]] + v[i] , f[n])
这就是他的状态转移方程。
因为他的每个物品只能用一次，所以为了避免重复使用所以我们从后开始遍历。以下是代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;

int v[100000],w[100000],f[100000];

int main(){
	int n,t;
	cin>>n>>t;
	int i = 0;
	for(i;i < t;i++) cin>>w[i] >> v[i];
	i = 0;
	int j = 0;
	for(;i < t;i++)
		for(j = n;j >= w[i];j--)
			f[j] = max(f[j],f[j - w[i]] + v[i]); 
	cout<<f[n];
	return 0;
}

完全背包

题目：完全背包
完全背包和0/1最大的区别就是可以重复使用，所以他就从头开始遍历。
他们状态转移方程是一样的
f[n] = max(f[n - w[i]] + v[i] , f[n])
以下是代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include<string>
using namespace std;
int v[10000],w[10000],f[100000];

int main() {
	int n,t;
	cin>>n >> t;
	int j ,i = 0;
	for(;i < t;i++) cin >> w[i] >> v[i];
	for(i = 0;i < t;i++)
		for(j = w[i];j <= n;j++)
			f[j] = max(f[j - w[i]] + v[i],f[j]);
	cout<<f[n];
	return 0;
}