【蓝桥杯】01背包问题

一、问题描述

有 N 个物品，并且每个物品都有一个重量 W 和一个价值 V。你有一个能装 M 重量的背包，问怎么装才能使所装的价值最大(每个物品只有一个)

输入：

输入的第一行包含两个整数 n, m，分别表示物品的个数和背包能装的重量

以后N行每行两个数 Wi 和 Vi,表示物品的重量和价值

输出：

输出1行，包含一个整数，表示最大价值。

样例输入： 3 5 2 3 3 5 4 7 样例输出： 8

二、解题思路

解题方法：动态规划

记 f(i, W)：当背包容量为 W 时，现有 i 件物品可以装，所能装入背包的最大值(即：f(3, 5))

那么现在分为两种情况：

a. 不装入第 i 件物品，f(i-1, W)

b. 装入第 i 件物品，f(i-1, W - w[i]) + v[i]

由此可以推出状态转移方程： $$f(i,W)=\{\begin{array}{llc}f(i-1,W)& \text{w[i]>W(物品太重)}& \\ max\{f(i-1,W),& f(i-1,W-w[i])+v[i]\}& \text{w[i]<=W}\end{array}$$ 即：

通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到

三、AC代码如下

#include<bits/stdc++.h> using namespace std; int dp[201][5001]; int main() { int n,m,z; cin>>n>>m; vector<int> w,v; for(int i=1;i<=n;i++){ cin>>z; w.push_back(z); cin>>z; v.push_back(z); } //规划最优解 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(j<w[i-1]){ dp[i][j] = dp[i-1][j]; continue; } dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1]); } } cout<<dp[n][m]<<endl; return 0; }