动态规划——01背包问题

写在前面

���于本人实力尚浅，接触算法没多久，写这篇blog仅仅是想要提升自己对算法的理解，如果各位读者发现什么错误，恳请指正，希望和大家一起进步。(●’◡’●)

DP(动态规划）核心讲解

状态表示：用一个数组f[][](数组可能是一维也可能是二维，根据具体题目具体分析）来表示某个集合，这个集合表示所有的做法，集合存的值就是对应做法的属性（一般是max，min，count）（换句话说：f[i][j]表示在限制i,j下做法的属性）

状态转移：本质上是一个优化的过程，就是不断更新状态。

01背包问题

题目

思路

重要变量说明:

f[][[]:用于状态表示；

w[]：记录每个物品的价值；

v][]：记录每个物品的体积；

1. 定义二维数组f[][],其中f[i][j]表示在前i个物品，背包容积为j的限制下所能装下的最大价值。这里的f[i][j]就是做法的集合，f[i][j]的值就是最大价值即属性。
2. 从i=1开始枚举，对于第i个物品，都有选和不选两种选择：
   • 如果不选第i个物品，那么状态转移方程为f[i][j]=f[i-1][j]
   • 如果选择第i个物品，那么状态转移方程为f[i][j]=f[i-1][j-v[i]]+w[i]
   • 我们因为要求最大价值，所以对上面两种情况去max即可

代码（不优化版，二维数组）

#includeusing namespace std;const int N=1010;int f[N][N],v[N],w[N];int main(){    int n,V;    cin>>n>>V;    for(int i=1;i>v[i]>>w[i];    for(int i=1;i            if(j-v[i]=0)       //可以装第i个物品                f[i][j]=f[i-1][j-v[i]]+w[i];        //状态转移            f[i][j]=max(f[i][j],f[i-1][j]);     //状态转移，两种情况取最大值        }    cout    int n,m;    scanf("%d%d",&n,&m);    for(int i = 1;i         for(int j = 0;j             f[i % 2][j] = f[(i - 1) % 2][j];            if(j = v[i]) f[i % 2][j] = max(f[i % 2][j],f[(i - 1) % 2][j - v[i]] + w[i]);        }    }    printf("%d",f[n % 2][m]);    return 0;}        for (int j = v[i]; j             f[j] = max(f[j], f[j - v[i]] + w[i]);        }    }        for (int j = m; j = v[i]; j--) {            f[j] = max(f[j], f[j - v[i]] + w[i]);        }    }    int n,m;    cinnm;    for(int i=1;i