DP——背包DP

动态规划——背包问题全总结

关于动态规划的背包问题，可分为：

• 0/1 背包问题
  
• 分组背包问题
  
• 多重背包问题
  
• 完全背包问题
  

1 0/1背包问题

问题描述

有 \(N\) 件物品和一个容量是 \(V\) 的背包。每件物品只能使用一次。
第 \(i\) 件物品的体积是 \(v_i\)，价值是 \(w_i\)。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输入描述：
第一行两个整数 \(N,V\)，用空格隔开，分别表示物品数量和背包容积。
接下来有 \(N\) 行，每行两个数 \(v_i, w_i\)，用空格分隔开，表示该物体的体积和价值。
输出描述：
输出一个整数，表示最大价值。
分析

引入一个 \((N+1) \times (V+1)\) 的二维数组 \(dp[][]\)。
\(dp[j]\) 表示把前 \(i\) 个物品【\(1,i\)】装入容量为 \(j\) 的背包中获得最大价值。
把每个 \(dp[j]\) 都看做一个背包；容量为 \(j\)，装 \(1 \sim i\) 这些物品，最后的 \(dp[N][V]\) 为问题答案。
dp 转移方程

• 第 \(i\) 个物品的体积比容量 \(j\) 还大，不能装进背包。直接继承前 \(i-1\) 个物品装进容量为 \(j\) 的背包情况即可，即
  

\[dp[j]=dp[i-1][j]\]

• 第 \(i\) 个物品的体积比容量 \(j\) 小，能装进背包，又可以分成两种情况：装或不装：
  ① 装第 \(i\) 个物品：
  

\[dp[j]=dp[i-1][j-v]+w\]
② 不装第 \(i\) 个物品：

\[dp[j]=dp[i-1][j]\]
取两者的最大值：

\[dp[j]=\max(dp[i-1][j],\ dp[i-1][j-v]+w)\]
递推代码（暴力做法）

[code]#include using namespace std;const int N = 1010;int w[N], v[N]; // 物品的价值和体积int dp[N][N];int solve(int n, int V) {    for (int i = 1; i  v >> w >> num;            for (int i = 1; i =v; j--)            for (int k = 1;j >= k * v&&k n>>sum;    int all=0;    for(int i=1;i>a>>b>>c;        for(int k=1;k0)        {            all++;            v[all]=a*c;            w[all]=b*c;        }    }    n=all;    for(int i=1;i=v;j--)            dp[j]=max(dp[j],dp[j-v]+w);                cout n >> sum;    for (int i = 1; i > a >> b;        t = sum / a;                for (int k = 1; k  0) { // 处理多余项            all++;            v[all] = a * t;            w[all] = b * t;        }    }    n = all;        // 0/1背包    for (int i = 1; i = v; j--)            dp[j] = max(dp[j], dp[j - v] + w);                cout >n>>sum;    while(n--)    {        cin>>v>>w;        for(int j=v;j

不错，里面软件多更新就更好了

用心讨论，共获提升！

收藏一下   不知道什么时候能用到