AcWing 2. 01背包问题
原题链接
简单
作者:
下次丕定
,
2024-03-24 17:32:53
,
所有人可见
,
阅读 2
算法思路
- 读取输入,包括物品数量
n
和背包容量 m
。
- 读取每件物品的体积
v[i]
和价值 w[i]
。
- 初始化一个二维数组
f[N][N]
,其中 f[i][j]
表示在前 i
件物品中,背包容量为 j
时的最大价值。
- 使用动态规划进行状态转移:
- 外层循环遍历每件物品,从第一件物品到第
n
件物品。
- 内层循环遍历所有可能的背包容量,从0到
m
。
- 对于每个状态
f[i][j]
,考虑两种情况:
- 不放入当前物品时的最大价值,即保持前
i-1
件物品的最大价值,即 f[i][j] = f[i-1][j]
。
- 放入当前物品时的最大价值,即将第
i
个物品放入背包,此时背包容量为 j - v[i]
,并且加上第 i
个物品的价值 w[i]
,即 f[i][j] = f[i-1][j-v[i]] + w[i]
。
- 综合考虑这两种情况,选择其中最大的值作为当前状态
f[i][j]
的最大价值。
- 输出最终状态
f[n][m]
,即在给定背包容量下可达到的最大价值。
C++ 代码
#include<iostream>
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++) //外层循环遍历每件物品
{
for(int j=0;j<=m;j++) //内层循环遍历所有可能的背包容量
{
// 默认情况下,当前物品不放入背包,保持上一个状态的最大价值不变
f[i][j]=f[i-1][j];
// 如果当前背包容量可以容纳当前物品
if(j>=v[i])
{
// 尝试将当前物品放入背包,比较放入和不放入的情况,取最大值作为当前状态的最大价值
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]); //考虑前 i-1 个物品时,背包容量为 j - v[i](即当前物品体积减去第 i 个物品的体积)时的最大价值
}
}
}
// 输出结果
cout<<f[n][m]<<endl;
return 0;
}