网站建设资讯

NEWS

网站建设资讯

如何理解背包问题

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

田家庵ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为创新互联公司的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:18982081108(备注:SSL证书合作)期待与您的合作!

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<

到此,相信大家对“如何理解背包问题”有了更深的了解,不妨来实际操作一番吧!这里是创新互联网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!


本文标题:如何理解背包问题
分享链接:http://njwzjz.com/article/jhooic.html