题目：
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤10000≤1000
0<vi,wi≤10000≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8算法分析：
以上面的题目为例：
f[i][j] : j是已经选择过后的背包的体积；
如果没有放入，背包的体积没有变化，即前一个前i-1个物品的体积也是j；
如果放入：j和前i-1的体积不同，j是前i-1个物品的体积改变而来的，即j-v[i]为前i-1个物品总体积；
如果还是不能理解的话，可以代入数据来写一下：
最后的f[4][5]就是最大价值；
代码：
#include<iostream>
#include<math.h>
using namespace std;
const int N = 1e4;
int v[N], w[N];
int f[N][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 = 0; j <= m; j++)
{
if (j < v[i])
f[i][j] = f[i - 1][j];
else
f[i][j]= max( f[i - 1][j],f[i - 1][j - v[i]] + w[i] );
}
}
cout << f[n][m] << endl;
}优化：
上面的代码我们用到是二维数组，如果数据较大，空间也会较大；怎么优化呢？
根据我们上面的分析，我们要求的 i ，只和 i-1 有关，所以我们只需要保存 i-1 的数据即可；
代码如下：
#include<iostream>
#include<math.h>
#include<cstring>
using namespace std;
const int N = 1e4;
int v[N], w[N];
int f[N],g[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 = 0; j <= m; j++)
{
if (j < v[i])
g[j] = f[j];
else
g[j]= max( f[j],f[j - v[i]] + w[i] );
}
memcpy(f, g, sizeof(g));
}
cout << f[m] << endl;
}我们只需修改一下代码即可:
for (int j = 0; j <= m; j++)
{
if (j < v[i])
g[j] = f[j];
else
g[j]= max( f[j],f[j - v[i]] + w[i] );
}
memcpy(f, g, sizeof(g));
f[j] 是前i-1 个物品的总体积；
g[j] 是前i 给物品的总体积；
我们只需要把g[j]求出来，然后更新f[j]即可；
不理解的话可以看一下模拟过程：
再次优化：
上面的优化过程我们用了g[N]的数组；
如何只用一个f[N]的数组来写？
只需要改变一下代码：
for (int j = m; j>=v[i]; j--)
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
#include<iostream>
#include<math.h>
using namespace std;
const int N = 1e4;
int v[N], w[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 = m; j>=v[i]; j--)
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;
}练习：
题目：
[NOIP2006 普及组] 开心的金明 - 洛谷
[NOIP2005 普及组] 采药 - 洛谷
AC代码：
（1）
#include<iostream>
#include<math.h>
using namespace std;
int f[100004],v[100000], p[100000];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
cin >> v[i] >> p[i];
for (int i = 1; i <= m; i++)
{
int t = 0;
for (int j = n; j >= v[i]; j--)
{
f[j] = max(f[j], f[j - v[i]] + p[i]*v[i]);
}
}
cout << f[n] << endl;
}（2）
#include<iostream>
#include<math.h>
using namespace std;
int f[1004], T[1000], W[1000];
int main()
{
int t, m;
cin >> t >> m;
for (int i = 1; i <= m; i++)
cin >> T[i] >> W[i];
for (int i = 1; i <= m; i++)
{
for (int j = t; j >= T[i]; j--)
{
f[j] = max(f[j], f[j - T[i]] + W[i]);
}
}
cout << f[t] << endl;
}完结！
