本篇内容主要讲解“如何理解背包问题”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“如何理解背包问题”吧!
0-1背包问题的二维bc
计算
安全
数据库
网络和加速
企业服务
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N]; //价值总和
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
//当选择0件物品时，价值总和为0，即f[0][0~m] = 0;
//由于已定义为全局变量，已经初始化为0，所以可以不写了。
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
//不选择第i个物品的方案
f[i][j]=f[i-1][j];
//选择第i个物品的方案可能不存在
//选择第i个物品————先去掉第i个物品，减去其重量再加上其价值。
if(j>=v[i]){
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
}
cout<<f[n][m]<<endl;
return 0;
}优化（转换成一维，滚动数组）
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];
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=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m]<<endl;
return 0;
}到此，相信大家对“如何理解背包问题”有了更深的了解，不妨来实际操作一番吧！这里是亿速云网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/zhengbaby66/blog/5012602
