当前位置：首页 > article >正文

【算法】----完全背包问题（动态规划）

article 2025/9/16 7:59:30

🌹作者:云小逸
📝个人主页:云小逸的主页
📝Github:云小逸的Github
🤟motto:要敢于一个人默默的面对自己，强大自己才是核心。不要等到什么都没有了，才下定决心去做。种一颗树，最好的时间是十年前，其次就是现在！学会自己和解，与过去和解，努力爱自己。==希望春天来之前，我们一起面朝大海，春暖花开！==🤟
👏专栏：C++👏 👏专栏：Java语言👏👏专栏：Linux学习👏
👏专栏：C语言初阶👏👏专栏：数据结构👏👏专栏：备战蓝桥杯👏

文章目录

前言
完全背包问题
- 问题定义
- 二维解法
- - 二维状态定义：
  - 二维状态方程：
  - 以下是C++语言的实现代码：
  - 代码优化：
- 一维解法
- - 一维状态定义：
  - 一维状态方程：
  - 以下是C++语言的实现代码：
- 总结
- 与01背包问题的区别：
最后

前言

今天我们接着上一篇博客继续学习背包问题：完全背包问题，这里将介绍完全背包问题的二维解法和一维解法，希望你可以喜欢。在这里插入图片描述 ——————————————————————————————

完全背包问题

完全背包问题是一个经典的动态规划问题，其解法主要有一维解法和二维解法两种。本文将分别介绍这两种解法，并给出C++语言的实现。

问题定义

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

二维解法

二维解法的思路是：对于每个物品，枚举背包容量和物品数量，计算背包容量为j，物品数量为k时的最大价值。状态转移方程为：f[j][k] = max(f[j][k], f[j-v[i]][k-1]+w[i])，其中f[j][k]表示背包容量为j，物品数量为k时的最大价值，v[i]表示第i个物品的体积，w[i]表示第i个物品的价值。

二维状态定义：

$f_{i,j}$ 表示前 $i$ 个物品，背包容量为 $j$ 时的最大价值。

二维状态方程：

$f_{i,j}=\max\{f_{i-1,j},f_{i,j-v_i}+w_i\}$ ，其中 $v_i$ 表示第 $i$ 个物品的体积， $w_i$ 表示第 $i$ 个物品的价值。

以下是C++语言的实现代码：

#include<bits/stdc++.h> //头文件
using namespace std;
const int N=1010; //常量定义，N为物品数量的上限
int n,m; //n为物品数量，m为背包容量
int v[N],w[N]; //v数组存储物品的体积，w数组存储物品的价值
int f[N][N]; //f数组存储背包容量为j，物品数量为k时的最大价值
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++) //枚举背包容量{for(int k=1;k<=j/v[i];k++) //枚举物品数量{f[j][k]=max(f[j][k],f[j-v[i]][k-1]+w[i]); //状态转移方程}}}cout<<f[m][m/v[n]]<<endl; //输出背包容量为m时的最大价值return 0; //程序结束
}

代码优化：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N]; // f[i][j]表示前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++) // 枚举前i个物品{for(int j=1;j<=m;j++) // 枚举背包容量{f[i][j]=f[i-1][j]; // 不将第i个物品放入背包中if(j>=v[i]) // 如果第i个物品的体积小于等于背包容量f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]); // 将第i个物品放入背包中}}cout<<f[n][m]<<endl; // 输出前n个物品放入容量为m的背包中所能获得的最大价值return 0;
}

一维解法

一维解法的思路是：对于每个物品，枚举背包容量，计算背包容量为j时的最大价值。状态转移方程为：f[j] = max(f[j], f[j-v[i]]+w[i])，其中f[j]表示背包容量为j时的最大价值，v[i]表示第i个物品的体积，w[i]表示第i个物品的价值。

一维状态定义：

$f_j$ 表示背包容量为 $j$ 时的最大价值。

一维状态方程：

$f_j=\max\{f_j,f_{j-v_i}+w_i\}$ ，其中 $v_i$ 表示第 $i$ 个物品的体积， $w_i$ 表示第 $i$ 个物品的价值。

以下是C++语言的实现代码：

#include<bits/stdc++.h> //头文件
using namespace std;
const int N=1010; //常量定义，N为物品数量的上限
int n,m; //n为物品数量，m为背包容量
int v[N],w[N]; //v数组存储物品的体积，w数组存储物品的价值
int f[N]; //f数组存储背包容量为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]=max(f[j],f[j-v[i]]+w[i]); //状态转移方程}}cout<<f[m]<<endl; //输出背包容量为m时的最大价值return 0; //程序结束
}

总结

完全背包问题是一个经典的动态规划问题，其解法主要有一维解法和二维解法两种。一维解法的空间复杂度为O(m)，时间复杂度为O(nm)，适用于物品数量较少的情况；二维解法的空间复杂度为O(m^{2)，时间复杂度为O(nm}2)，适用于物品数量较多的情况。

与01背包问题的区别：

完全背包问题和01背包问题是两个经典的背包问题，它们之间的区别主要体现在选择物品的方式上。
01背包问题：每件物品最多只能选择一次，要么放入背包，要么不放。因此，对于第 $i$ 件物品，只有两种选择，放入背包或者不放入背包。
完全背包问题：每件物品可以选择无限次，即可以放入背包中多次。因此，对于第 $i$ 件物品，可以选择放入背包中 $0$ 次、 $1$ 次、 $2$ 次、…… 直到不能再放为止，因此有无限个选择。
因此，在状态转移方程上，完全背包问题与01背包问题的区别在于：
01背包问题：
$dp[i][j]=\max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])$
完全背包问题：
$dp[i][j]=\max(dp[i-1][j],dp[i][j-v[i]]+w[i])$
其中 $d p [i] [j]$ 表示前 $i$ 个物品放入容量为 $j$ 的背包中所能获得的最大价值， $v [i]$ 表示第 $i$ 件物品的体积， $w [i]$ 表示第 $i$ 件物品的价值。