题目来源
本题来源为：
题目描述
题目解析
我们分析一下本道题目，体积为5，有三个物品。
有两个问题：
1.求这个背包至多能装多大价值的物品？
2.若背包恰好装满，求至多能装多大价值的物品？
这两个问题区别就是，第一个问题背包可以装满可以不装满
而第二个问题是恰好装满。
算法原理
我们先说一下什么是背包问题：
你现在有一个背包，地上有一堆物品，每个物品有自己对应的体积与价值，而每个背包的容量有限，你需要在保证自己的书包容量的同时保障价值最大。这就是背包问题。
背包问题分为好多种：
而01背包和完全背包为最为常见的两种。
01背包就是里面的物品只能选一次或者不选。
完全背包是里面的物品可以没有次数限制。
问题1.1.状态表示
经验+题目要求
这里不能用一维而是要用二维dp表，因为不仅要保证价值还要保证物品的容量，因此用二维的dp表
对于本题而言就是：
dp[i][j]表示：从前i个物品中挑选，总体积不超过j,所有选法中，能挑选出来的最大价值
2.状态转移方程
还是根据最后一步的情况来进行情况讨论
因此状态方程为：
dp[i][j]=dp[i-1][j]; if(j>=v[i]&&dp[i-1][j-v[i]]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
3.初始化
跟之前一样，在原数组加一行一列
4.填表顺序
从上往下
5.返回值
dp[n][v]
问题2.1.状态表示
问题二跟问题一基本一样：
经验+题目要求
对于本题而言就是：
dp[i][j]表示：从前i个物品中挑选，总体积正好等于j,所有选法中，能挑选出来的最大价值
2.状态转移方程
还是根据最后一步的情况来进行情况讨论
因此状态方程为：
dp[i][j]=dp[i-1][j]; if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
3.初始化
跟之前一样，在原数组加一行一列
4.填表顺序
从上往下
5.返回值
dp[n][v]
代码实现
动态规划的代码基本就是固定的四步：
1.创建dp表 2.初始化 3.填表 4.返回值
本题完整代码实现：
#include <iostream> #include <string.h> using namespace std; const int N=1010; int n,V,v[N],w[N]; int dp[N][N]; int main() { //读入数据 cin>>n>>V; for(int i=1;i<=n;i++) { cin>>v[i]>>w[i]; } //解决第一问： for(int i=1;i<=n;i++) { for(int j=1;j<=V;j++) { dp[i][j]=dp[i-1][j]; if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]); } } cout<<dp[n][V]<<endl; //解决第二问： memset(dp,0,sizeof dp); for(int j=1;j<=V;j++) dp[0][j]=-1; for(int i=1;i<=n;i++) { for(int j=1;j<=V;j++) { dp[i][j]=dp[i-1][j]; if(j>=v[i]&&dp[i-1][j-v[i]]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]); } } cout<<(dp[n][V]==-1?0:dp[n][V])<<endl; }
空间优化：
空间优化有两种优化方式：
1.利用滚动数组进行优化
2.直接在原来的代码上进行修改
代码实现：
#include <iostream> #include <string.h> using namespace std; const int N=1010; int n,V,v[N],w[N]; int dp[N]; int main() { //读入数据 cin>>n>>V; for(int i=1;i<=n;i++) { cin>>v[i]>>w[i]; } //解决第一问： for(int i=1;i<=n;i++) { for(int j=V;j>=v[i];j--) dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } cout<<dp[V]<<endl; //解决第二问： memset(dp,0,sizeof (dp)); for(int j=1;j<=V;j++) dp[j]=-1; for(int i=1;i<=n;i++) { for(int j=V;j>=v[i];j--) { if(dp[j-v[i]]!=-1) dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } } cout<<(dp[V]==-1?0:dp[V])<<endl; }
