01背包(实验报告)

本文最后更新于:10 天前

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.程序运行结果

img

三、复杂度分析

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

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


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!