背包问题分为01背包和完全背包，下面分别分析其解法
01背包
有n件物品，每件物品的重量为w[i]，价值为c[i]。现在需要选出若干件物品放入一个容量为V的背包中，使得再选入背包的物品重量和不超过容量V的前提下，让背包中物品价值和最大，求最大价值(1<=n<=20)
DFS:
/*每件物品有放与不放两种选择，这就形成了二叉树的两个分支，
利用深度遍历可以遍历到所有情况*/
#include<iostream>
using namespace std;
const int maxn = 30;
int n, V, maxValue = 0;//n为物品件数
int w[maxn], c[maxn];
void DFS(int index, int sumW, int sumC) { //sumW.sumC分别为当前重量和和当前价值和
if (index == n) { //完成遍历
if (sumW <= V && sumC > maxValue) {
maxValue = sumC;//当不超过V时更新最大价值
}
return;
}
DFS(index + 1, sumW, sumC);//不选第index件物品，进入下一个左边一个分支
DFS(index + 1, sumW + w[index], sumC + c[index]);//选第index件物品，进入右边一个分支
}
int main() {
cin >> n >> V;
for (int i = 0; i < n; i++)
cin >> w[i];
for (int i = 0; i < n; i++)
cin >> c[i];
DFS(0, 0, 0);
cout << maxValue;
return 0;
}
动态规划：
/*使用DFS要枚举每一件物品，那么n件物品就有2^n中情况，时间复杂度不太理想
现在用动态规划法来优化，以dp[i][v]来表示恰好装入容量为v的背包的最大价值
（1）不放第i件物品，那么最大价值与前面i-1件物品有关，即dp[i-1][v]
（2）放第i件物品，最大价值与也与前一件物品有关，即dp[i-1][v-w[i]]+c[i]
故得到转移方程 dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i])
*/
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100;
const int maxv = 1000;
int w[maxn], c[maxn], dp[maxn][maxv];
int main() {
int n, V;
cin >> n >> V;
for (int i = 0; i < n; i++)
cin >> w[i];
for (int i = 0; i < n; i++)
cin >> c[i];
//边界
for (int v = 0; v <= V; v++) {
dp[0][v] = 0;
}
for (int i = 1; i <= n; i++) {
for (int v = w[i]; v <= V; v++) {
dp[i][v] = max(dp[i - 1][v], dp[i - 1][v - w[i]] + c[i]);
}
}
int max = 0;
for (int i = 0; i < n; i++) {
if (dp[i][V] > max)
max = dp[i][V];
}
cout << max;
}
使用滚动数组法可以进一步优化空间复杂度
/*dp[i][v]只与dp[i-1][v-w[i]]和dp[i-1][v]有关，
所以当求解dp[i+1][]时dp[i-1][]就用不到了，
故转移方程为dp[v]=max(dp[v],dp[v-w[i]]+c[i])，但v的枚举方向改为V到0
*/
for (int i = 1; i <= n; i++) {
for (v = V; v >= w[i]; v--) {
dp[v] = max(dp[v], dp[v - w[i]] + c[i]);
}
}
完全背包
有n种物品，每种物品重量为w[i],价值为c[i]，现有一个容量为V的背包，问如何选取物品放入背包，使得总价值最大，其中每个物品有无穷件
动态规划：
/*完全背包和01背包的区别就在每种物品数量上，所以动态规划有很多相似点
(1)不放第i种，dp[i][v]=dp[i-1][v]
(2)放第i种，之后不一定就是i-1件，而是还可以继续放第i种，dp[i][v]=dp[i][v-w[i]]+c[i]
状态转移方程：dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
*/
- 完全背包问题和贪心问题的分析：
贪心问题通常不同种物品的重量相等，但价值不等，故优先把价值最大的物品装进背包
而完全背包问题因为要考虑每种的重量，故不可先把价值最大的放进背包
下面给一道贪心算法例题以供辨析
假如有三种月饼，其库存量分别为18、15、10万吨，总售价分别是75，72，45亿元，如果市场最大需求量只有20万吨，该如何销售
很明显应该是把单价最高的商品优先销售
