Word直接粘贴的，各式有点乱

软件工程系项目/实验报告

姓名	xx	学号	xxx
专业班级	软件xx	指导教师	xx
课程名称	算法分析与设计
项目/实验 名称	0-1背包问题

一、解决方案的分析与设计

问题描述：

一个最大容量为 Weight 的背包和 N 个物品，每个物品有对应的重量和属性，分别用weight[]和 val[] 表示。求当背包重量为 Weight 时，最多能装下物品的价值为多少？

第一步：设计备忘录

​ 设计一个二维数组作为程序的备忘录： dp[][]， dp[i][w]表示在前 i 个物品中选择，背包最大能承受重量为 w，能装下物品的最大价值。比如dp[2][5] = 10 表示在前2个物品中选择，背包最大容量为5，能装下物品的最大价值为10。

​ 按照这个定义，最终的答案则为 dp[N][Weight]。

第二步：求状态转移方程

​ 根据 dp[i][w] 的定义，如果不把第 i 个物品放进背包，则为 dp[i-1][w]；如果把第 i 个物品放进背包，则为 dp[i-1][w-weight[i-1]] + val[i-1]。后面的方程表示第 i 个物品放进背包，则前 i-1 个物品也选择过了，且背包剩余的重量的weight[i-1]，最后需要加上第 i 个物品的价值，则可求出结果。

​ 所以状态转移方程为 max(dp[i-1][w], dp[i-1][w-weight[i-1]] + val[i-1])。

第三步：备忘录初始化

​ 根据 dp[i][w] 定义可知，dp[0][…] 和 dp[…][0] 表示不选择物品和背包不能装东西时的状态。所以这两个表达式都应该初始化为0。

第四步： 伪代码

int dp[N+1][Weight+1]
dp[0][…] = 0
dp[…][0] = 0
for i 1 to N:
for j 1 to Weight:
	dp[i][j] = max (put item i into bag, item i not in the bag)
return dp[N] [Weight]

第五步：处理边界情况

​ 在对背包容量进行遍历时，需要注意，如果第 i 个物品装入背包，背包剩余的重量小于0，则这个物品不能放入背包。

代码打印出了整个dp备忘录数组，最后应返回的结果为dp[N][Weight]，具体见代码注释。

二、解决方案的程序实现

1.程序代码

\#include<bits/stdc++.h>
 using namespace std;


 /**
 \* dp[][] 数组定义
 \*   dp[i][w]: 在前 i 个物品里选择，重量不超过 w 的物品的 最大价值
 \*   dp[N][W]: 在前 N 个物品中选择，重量不超过 W 的物品的 最大价值
 \* 数组初始化
 \*   baseCase1 dp[0][...] 不选择物品，则最大价值为0
 \*   baseCase2 dp[...][0] 选择的物品重量不超过0 -> 不选择物品，则最大价值为0
 *
 \* @param  W     最大价值
 \* @param  N     物品数编号
 \* @param  wt[]   重量数组
 \* @param  val[]   价值数组
 \* @return
 */
 int knapsack(int Weight, int N, vector<int> &weight, vector<int> &val) {
   // 初始化所有元素为0， 可以节省 dp[0][...] 和 dp[...][0] 初始化为0的步骤
   vector<vector<int>> dp(N + 1, vector<int>(Weight + 1, 0));
   for ( int i = 1; i <= N; i++ ) { // 遍历物品
     for ( int j = 1; j <= Weight; j++ ) { // 遍历背包容量
       if ( j - weight[i-1]< 0 ) {
         // 背包容量不足以放下第i个物品，不放进背包
         dp[i][j] = dp[i-1][j];
       } else {
         dp[i][j] = max(
             // 第i个物品不放进背包
             dp[i-1][j],
             //第i个物品放进背包
             dp[i-1][j-weight[i-1]] + val[i-1]
         );
       }
       cout << dp[i][j] << " "; // 打印dp数组
     }
     cout << endl;
   }

   return dp[N][Weight];
 }

 int main() {
   vector<int> weight = {1, 3, 5};
   vector<int> val = {15, 20, 30};
   int Weight = 6;
   int N = 3;
   int ans = knapsack(Weight, N, weight, val);
 //  cout << ans << endl;
  return 0;
 }

2.程序运行结果

三、复杂度分析

代码嵌套了两个 for 循环，分别对 N 个物品的遍历和对 Weight 重量的遍历；dp[][]数组作为备忘录，最终的结果为 dp[N][Weight]。

则时间复杂度和空间复杂度均为 O( N * Weight )。