如何理解背包问题

本篇内容主要讲解"如何理解背包问题"，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习"如何理解背包问题"吧!

0-1背包问题的二维bc

#include #include #include #include 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<
优化（转换成一维，滚动数组）
#include #include #include #include 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<
到此，相信大家对"如何理解背包问题"有了更深的了解，不妨来实际操作一番吧！这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！