完全背包问题的解决方法：

闫氏 DP\ DP DP 分析法:
通过集合划分，我们可以得到第 i\ i i 个物品有两种状态：
 1.选 1−T\ 1 - T 1−T 个，最优解为前 i−1\ i− 1 i−1 个物品的所有选择中，还能选取当前 k\ k k 个第i\ i i 个物品的最大价值加上 k\ k k 个第 i\ i i 个物品本身的价值，即
dp[i][j]=max(dp[i][j],dp[i−1][j−k∗v[i]]+k∗w[i]),(1≤k≤T)\ dp[ i ][ j ]= max( dp[ i][ j], dp[ i− 1][ j− k∗ v[i]]+k∗w[i]),(1≤k≤T) dp[i][j]=max(dp[i][j],dp[i−1][j−k∗v[i]]+k∗w[i]),(1≤k≤T)
 2.不选，最优解为前i−1\ i−1 i−1个物品的所有选择中的最大价值，即 dp[i][j]=dp[i−1][j]\ dp[i][j]=dp[i−1][j] dp[i][j]=dp[i−1][j]
若使用枚举的方式来选取1−k\ 1−k 1−k个物品 i的情况，会超时，故需分析当前的状态转移方程能否被优化。
我们令该朴素转移方程为 A式：
dp[i][j]=max(dp[i−1][j],dp[i−1][j−v]+w,dp[i−1][j−2v]+2w,⋯,dp[i−1][j−kv]+kw)\ dp[i][j]=max(dp[i−1][j],dp[i−1][j−v]+w,dp[i−1][j−2v]+2w,⋯,dp[i−1][j−kv]+kw) dp[i][j]=max(dp[i−1][j],dp[i−1][j−v]+w,dp[i−1][j−2v]+2w,⋯,dp[i−1][j−kv]+kw)
将左式的j\ j j替换成j−v\ j−v j−v后，得到 B式：
dp[i][j−v]=max(dp[i−1][j−v],dp[i−1][j−2v]+w,⋯,dp[i−1][j−kv]+(k−1)w)\ dp[i][j−v]=max(dp[i−1][j−v],dp[i−1][j−2v]+w,⋯,dp[i−1][j−kv]+(k−1)w) dp[i][j−v]=max(dp[i−1][j−v],dp[i−1][j−2v]+w,⋯,dp[i−1][j−kv]+(k−1)w)
仔细观察可以发现，A式从第二项开始与 B 式很相似，两者之间的差异仅为一个 w。
因此，将 A式右边第二项开始替换成 B 式加上一个 w 后，可得 C式：
dp[i][j]=max(dp[i−1][j],dp[i][j−v]+w)\ dp[i][j]=max(dp[i−1][j],dp[i][j−v]+w) dp[i][j]=max(dp[i−1][j],dp[i][j−v]+w)

3. 完全背包问题

#include 
#include using namespace std;const int N = 1010;int n, m;
int v[N], w[N];
int f[N][N];//表示从前i个物品中选,总体积不超过j的方案的集合int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];for (int i = 1; i <= n; i ++ )//物品从第1件开始{for (int j = 0; j <= m; j ++ )//空间从0开始{f[i][j] = f[i-1][j];if( j >= v [i] ){f[i][j] = max(f[i-1][j], f[i][j - v[i]] + w[i]);//公式推导出来的}}}cout << f[n][m] << endl;return 0;
}

改成一维,如下:

#include 
#include using namespace std;const int N = 1010;int n, m;
int v[N], w[N];
int f[N];//不超过总体积j的方案的集合int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];for (int i = 1; i <= n; i ++ ){for (int j = v[i]; j <= m; j ++ ){//f[j] = f[j];  等式右边的f[j]表示 : 未更新前的,前i个物品中选,总体积不超过j的方案的集合 ; 等式左边表示更新后的 前i个物品中选,总体积不超过j的方案的集合。所以，与f[i][j] = f[i-1][j];等效f[j] = max(f[j], f[j - v[i]] + w[i]);//cout<