题意： 即是给你一个容量M的包，有N件物品，每件物品有分别对应的 价值value 以及 重量weight .然后在不超过该背包容量的情况下能得到的最大价值为多少？思路： 由于这是最基础的问题，所以就记录当对 01背包状态转移方程式的 理解。 对于动态规划来说，首先要知道我们要确定哪些状态量。然后再基于这些状态量进行状态转移得到我们最后希望得到的答案。 比如对于序列求最值来说我们习惯记录最后位取的是谁（即末位j），那么同理我们也可以记录我们当前选的是哪一种 物品。同时容量在状态中是必不可少的，所以最后为 \(二维dp[i][j],i为第i种物品，j为剩余容量\) 所有有对应伪代码：
for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) if j < w[ i ] , 则 dp[ i + 1 ][ j ] = dp[ i ][ j ]；//这一步在后面可以与下面合并掉 else dp[ i + 1 ][ j ] = max ( dp[ i ][ j ]， dp [i ][ j - w[ i ]] + v[ i ]）；但是如果种类过多，容量过大则会出现MLE问题。所以我们简化为一维形式。对于取哪一个物品实际上我们可以不用记录，因为我们最后只需要知道当容量为M时，最值即可，所以设\(一维dp[j],表容量\)
for(int i=1;i<=n;i++) for(int j=m;j>=w[i];j--) dp[j] = max ( dp[j] , dp[ j - w[i] ] + v[i] );所以最后code：
#include <cstdio> #include <algorithm> #include <cmath> const int maxn =2e5; const int maxm = 4e3; using namespace std; int dp[maxn];//一维 struct Goods { int w,v; }goods[maxm]; int main(){ int n,m; while(~scanf("%d %d",&n,&m)){ for(int i=0;i<n;i++){ scanf("%d %d",&goods[i].w,&goods[i].v); } for(int i=0;i<n;i++){ for(int j=m;j>=goods[i].w;j--){ dp[j] = max(dp[j],dp[j-goods[i].w]+goods[i].v); } } printf("%d\n",dp[m]); } }转载于:https://www.cnblogs.com/Tianwell/p/11408408.html
