中级光能
那位大佬能给我说一下01背包是啥？？？
中级天翼
我上过，字太多了，无奈地献出讲义：
一、动态规划
动态规划可以看成一个复杂的递推式，对于递推式而言，有几个特征：
递推项，递推起始项，递推关系，递推终点。
在动态规划中，递推项称为状态；
递推的起始项为边界；
递推终点称为目标；
递推关系为状态转移方程。
注：
动态规划的最优化原理：
子问题的局部最优解导致整个问题的全局最优。
动态规划的无后效性原则
某阶段的状态一旦确定，不会受前后状态影响，当前状态是此前历史的一个完整的总结。
二、01背包
问题模型
给定N个物品，其中第i个物品的体积Vi，价值为Wi。有一容积为M的背包，要求选择一些物品放入背包，在使得物品总体积不超过M的前提下，物品的价值总和最大。
状态：用二维数组表示状态
f[i][j]，将前i件物品放入容量为j的背包能获得最大价值；
边界：注意用循环赋值边界
f[0][j]=0,将前0件物品放入容量为j的背包能获得的最大价值;
目标
f[n][m],将n件物品放入总容量为m的背包能获得的最大价值;
转移方程：分情况讨论
1.j>=Vi
即第i个物品能放入容量为j的背包，此时第i个物品可以选，也可以不选。
2.j<Vi
即第i个物品不能放入容量为j的背包，此时问题转化成前i-1个物品放入容量为j的背包最大价值。
综上：
f[i][j]=f[i-1][j] j<Vi
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]) j>=vi
01背包降维
当题目中给出的数据范围比较大时，我们会发现无法定义那么大的数组，这时候我们考虑降维。
即本来用的二维数组表示状态，现在用一位数组
首先观察上述图片，发现当我们在求第i 行第 j 列的状态 f[i][j]时，我们可以发现它只会用到上一行同一列及其左边的状态，所以我们可以将一个二维数组压缩成一维数组。
注意：
虽然实现了降维，降低了空间复杂度，但是时间复杂度仍然是O(n*m)
采纳谢谢！！！
PS:我是被禁言过N次的。。。为了保险起见，我把课堂题代码删了。因此而造成不便，敬请谅解。
中级光能
ding
初级启示者
你确定你能听懂？
问度娘呀
缔造者之神
1
中级天翼
一、动态规划
动态规划可以看成一个复杂的递推式，对于递推式而言，有几个特征：
递推项，递推起始项，递推关系，递推终点。
在动态规划中，递推项称为状态；
递推的起始项为边界；
递推终点称为目标；
递推关系为状态转移方程。
注：
动态规划的最优化原理：
子问题的局部最优解导致整个问题的全局最优。
动态规划的无后效性原则
某阶段的状态一旦确定，不会受前后状态影响，当前状态是此前历史的一个完整的总结。
二、01背包
问题模型
给定N个物品，其中第i个物品的体积Vi，价值为Wi。有一容积为M的背包，要求选择一些物品放入背包，在使得物品总体积不超过M的前提下，物品的价值总和最大。
状态：用二维数组表示状态
f[i][j]，将前i件物品放入容量为j的背包能获得最大价值；
边界：注意用循环赋值边界
f[0][j]=0,将前0件物品放入容量为j的背包能获得的最大价值;
目标
f[n][m],将n件物品放入总容量为m的背包能获得的最大价值;
转移方程：分情况讨论
1.j>=Vi
即第i个物品能放入容量为j的背包，此时第i个物品可以选，也可以不选。
2.j<Vi
即第i个物品不能放入容量为j的背包，此时问题转化成前i-1个物品放入容量为j的背包最大价值。
综上：
f[i][j]=f[i-1][j] j<Vi
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]) j>=vi
当题目中给出的数据范围比较大时，我们会发现无法定义那么大的数组，这时候我们考虑降维。
即本来用的二维数组表示状态，现在用一位数组
首先观察上述图片，发现当我们在求第i 行第 j 列的状态 f[i][j]时，我们可以发现它只会用到上一行同一列及其左边的状态，所以我们可以将一个二维数组压缩成一维数组。
状态：表示容量为j的背包的最大价值和
f[j]
边界：
for(int i=0;i<=V;i++)
f[i]=0;
状态转移方程：
for(int i=1;i<=n;i++)
for(int j=V;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
目标： f[V]。
新手天翼
一、动态规划
动态规划可以看成一个复杂的递推式，对于递推式而言，有几个特征：
递推项，递推起始项，递推关系，递推终点。
在动态规划中，递推项称为状态；
递推的起始项为边界；
递推终点称为目标；
递推关系为状态转移方程。
注：
动态规划的最优化原理：
子问题的局部最优解导致整个问题的全局最优。
动态规划的无后效性原则
某阶段的状态一旦确定，不会受前后状态影响，当前状态是此前历史的一个完整的总结。
二、01背包
问题模型
给定N个物品，其中第i个物品的体积Vi，价值为Wi。有一容积为M的背包，要求选择一些物品放入背包，在使得物品总体积不超过M的前提下，物品的价值总和最大。
状态：用二维数组表示状态
f[i][j]，将前i件物品放入容量为j的背包能获得最大价值；
边界：注意用循环赋值边界
f[0][j]=0,将前0件物品放入容量为j的背包能获得的最大价值;
目标
f[n][m],将n件物品放入总容量为m的背包能获得的最大价值;
转移方程：分情况讨论
1.j>=Vi
即第i个物品能放入容量为j的背包，此时第i个物品可以选，也可以不选。
2.j<Vi
即第i个物品不能放入容量为j的背包，此时问题转化成前i-1个物品放入容量为j的背包最大价值。
综上：
f[i][j]=f[i-1][j] j<Vi
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]) j>=vi
课堂题代码
1269 采药
/**
只考虑第i件物品：
第i件物品不放入其中：f[i-1][j]
第i件物品放入其中：f[i-1][j-t[i]] + w[i]
f[i][j] = max(f[i-1][j], f[i-1][j-t[i]] + w[i]);
*/
#include <iostream>
using namespace std;
int t[110], w[110];
int f[110][1010];//f[i][j]:前i件物品放入容量为j的背包中的最大价值
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=1; j<=T; j++) {
if(j>=t[i])
f[i][j] = max(f[i-1][j], f[i-1][j-t[i]] + w[i]);
else
f[i][j] = f[i-1][j];
}
}
cout << f[m][T];
return 0;
}
3133 装水桶
这道题中，物品的价值和体积都是体积。这是变形的01背包。
#include <iostream>
using namespace std;
int t[40];
int f[40][20010];//f[i][j]:前i件物品放入容量为j的背包中的最大价值
int main() {
int T, m;
cin >> T >> m;
for(int i=1; i<=m; i++)
cin >> t[i];
for(int i=1; i<=m; i++) {
for(int j=1; j<=T; j++) {
if(j>=t[i])
f[i][j] = max(f[i-1][j], f[i-1][j-t[i]] + t[i]);
else
f[i][j] = f[i-1][j];
}
}
cout << T - f[m][T];
return 0;
}
