完全背包问题
有 N种物品和一个容量是 V的背包，每种物品都有无限件可用。
第 i种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10
我们会根据01背包自然而然的想到会用三次循环，但是这里的数据是1000，三次循环很显然会TLE。
#include
using namespace std ;
const int N = 1010 ;
int f[N][N] ;
int w[N] , v[N] ;
int main()
{
int n , m ;
cin >> n >> m ;
for(int i = 1 ; i <= n ; i++)
{
cin >> v[i] >> w[i] ;
}
for(int i = 1 ; i <= n ; ++i)
{
for(int j = 1 ; j <= m ; ++j)
{
f[i][j] = f[i-1][j] ;
for(int 1 = 0 ; j - v[i] * k >= 0 ; k++)
{
f[i][j] = max(f[i][j] , f[i-1][j-k*v[i]] + k*w[i]) ;
}
}
}
cout << f[i][j] << endl ;
return 0 ;
}
所以我们后面开始考虑用二轮循环进行优化 。
状态表示：同01背包问题，dp[i] [j] 表示的是，使用前i个物品并且体积不超过j的所能够实现的最大价值。
状态属性：max
base case：同01背包问题
状态转移：这可以通过小学数学来进行一个推导。
f[i][j] = max(f[i-1][j] , f[i-1][j-v[i]] + w[i] , f[i-1][j-2*v[i]] + 2*w[i] + .....)
f[i][j-v[i]] = max(f[i-1][j-v[i]] , f[i-1][j-2*v[i]]+2*w[i] + .....)
//所以由一式与二式相消可知
f[i][j] = max(f[i-1][j] , f[i][j-v[i]]+ w[i]) ;
错误的做法：
#include
using namespace std ;
const int N = 1010 ;
int f[N][N] ;
int w[N] , v[N] ;
int main()
{
int n , m ;
cin >> n >> m ;
for(int i = 1 ; i <= n ; ++i)
{
cin >> v[i] >> w[i] ;
}
for(int i = 1 ; i <= n ;++i)
{
for(int j = 1 ; j <= m ; ++j)
{
if(j >= v[i])
{
f[i][j] = max(f[i-1][j] , f[i][j-v[i]]+w[i]) ; // 注意这样写是错的，这样会导致当j< v[i]的时候，没有东西进行迭代
}
}
}
cout << f[n][m] << endl ;
return 0 ;
}
正确的做法：
#include
using namespace std ;
const int N = 1010 ;
int f[N][N] ;
int w[N] , v[N] ;
int main()
{
int n , m ;
cin >> n >> m ;
for(int i = 1 ; i <= n ; ++i)
{
cin >> v[i] >> w[i] ;
}
for(int i = 1 ; i <= n ;++i)
{
for(int j = 1 ; j <= m ; ++j)
{
f[i][j] = f[i-1][j] ;
if(j >= v[i])
{
f[i][j] = max(f[i][j] , f[i][j-v[i]]+w[i]) ;
}
}
}
cout << f[n][m] << endl ;
return 0 ;
}
形同01背包问题，由于完全背包问题也仅仅是用到了前一轮的值，所以我们完全可以进行一维的优化。
#include
using namespace std ;
const int N = 1010 ;
int w[N] , v[N] ;
int f[N] ;
int main()
{
int n , m ;
cin >> n >> m ;
for(int i = 1 ; i <= n ; ++i)
{
cin >> v[i] >> w[i] ;
}
for(int i = 1 ; i <= n ; ++i)
{
for(int j = v[i] ; j <= m ; ++j)
{
f[j] = max(f[j] , f[j-v[i]]+w[i]) ;
}
}
cout << f[m] << endl ;
return 0 ;
}
有的人肯定又会进行纠结，纠结的点就是在于j的循环顺序的问题，为什么这一次的j就是由小到大进行穷举的呢？
我们说一维的运算其实就是对二维的简化(这…. 好像是说了一句废话…..)，其实意思就是一维的逻辑就是二维的逻辑。我们反过来看二维的dp转移方程就知道了。
f[i][j] = max(f[i-1][j] , f[i][j-v[i]]+w[i]) ;
我们发现对于f[i-1] [j]来说，一维的毋庸置疑就是上一轮遗留下来的，对于f[i] [j-v[i]] + w[i] 来说，在一维的状态下必须是由该轮转移下来的，所以必须由小到大进行列举，小的赋值完了之后，才轮到大的进行赋值。
其实完全背包问题可以延申很多，例如我们之前说过的，整数划分问题。就可以理解为是一种完全背包问题。
