例题1：
有 N 个物品，从 1 到 N 编号。对于每个 i（1≤i≤N），物品 i 的重量是 wi 价值是 vi。
太郎决定从 N 个物品里选一些放进背包带回家。太郎的背包的容量是 W，因此放进背包的物品的总重量不能超过 W。
求太郎带回家的物品的总价值可能达到的最大值。
1. 贪心解法：
优先拿价值高的物品，优先拿单位重量价值高的物品。
2. 动态规划解法：
思路
把N个物品按编号从小到大的顺序排成一行，从物品1开始，决定每个物品能不能选。
令f[i][j]为从前i个物品中选一些，所选物品的总重不超过j，所选物品的总价值，问题的答案就是f[n][m]。
递推式：
若j<w[i]则不能选物品i，为
若j>=w[i]，则能选物品i，为
边界条件:
代码
普通写法：
#include <bits/stdc++.h>
using namespace std;
long long f[105][100005];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int w, v;
cin >> w >> v;
for (int j = 0; j < w; j++)
{
f[i][j] = f[i - 1][j];
}
for (int j = w; j <= m; j++)
{
f[i][j] = max(f[i - 1][j], f[i - 1][j - w] + v);
}
}
cout << f[n][m];
return 0;
}
- 时间复杂度：
- 空间复杂度：
节省空间的写法(一)：
#include <bits/stdc++.h>
using namespace std;
long long f[105][100005];
int main()
{
int n, m;
cin >> n >> m;
int x = 0, y = 1;
for (int i = 1; i <= n; i++)
{
int w, v;
cin >> w >> v;
for (int j = 0; j < w; j++)
f[y][j] = f[x][j];
for (int j = w; j <= m; j++)
f[y][j] = max(f[x][j], f[x][j - w] + v);
swap(x, y);
}
cout << f[x][m];
return 0;
}
节省空间的写法(二)：
#include <bits/stdc++.h>
using namespace std;
long long f[100005];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int w, v;
cin >> w >> v;
for (int j = m; j >= w; j--)
f[j] = max(f[j], f[j - w] + v);
}
cout << f[m];
return 0;
}
例题2：
有 N 个物品，编号 1,2,…,N。对于每个 i（1≤i≤N），物品 i 的重量是 wi，价值是 vi。
有一个背包，容量是 M。要从这 N 物品中选一些装进背包，物品的重量之和不能超过 M。
求装进背包里的物品的价值之和可能达到的最大值。
思路
递推式
如果j<v[i]
如果j>=v[i]