背包问题代码合集(C/C++)

这篇具有很好参考价值的文章主要介绍了背包问题代码合集(C/C++)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1  01背包问题

2  完全背包问题

3  多重背包问题

4  分组背包问题


1  01背包问题

N件物品和一个容量是V的背包。每件物品只能使用一次。

物品的体积是,价值是。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。

输出最大价值。

输入格式

第一行两个整数,NV,用空格隔开,分别表示物品数量和背包容积。

接下来有N行,每行两个整数,,用空格隔开,分别表示第i件物品的体积和价值。

输出格式

输出一个整数,表示最大价值。

数据范围

0<N,V≤1000

  解决方案1:二维数组

for(int i = 1; i <= n; i++)
{
    for(int j = 1; j <= m; j++)
    {
         //  当前背包容量装不进第i个物品,则价值等于前i-1个物品
         if(j < v[i])  f[i][j] = f[i - 1][j];
         // 能装,需进行决策是否选择第i个物品
         else   f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
    }           
}
 
        

解决方案2:一维数组(推荐) 

for(int i = 1; i <= n; i++) 
{
        int v, w;
        cin >> v >> w;      // 边输入边处理
        for(int j = m; j >= v; j--)
            f[j] = max(f[j], f[j - v] + w);
}

2  完全背包问题

N种物品和一个容量是V的背包。每种物品都有无限件可用。

第 种物品的体积是,价值是。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。

输出最大价值。

输入格式

第一行两个整数,NV,用空格隔开,分别表示物品种数和背包容积。

接下来有N行,每行两个整数,,用空格隔开,分别表示第i种物品的体积和价值。

输出格式

输出一个整数,表示最大价值。

数据范围

0<N,V≤1000

for(int i = 1 ; i<=n ;i++)
{
    int v,w; 
	cin>>v>>w;
	for(int j = v; j<=m ;j++)//正向循环
    {
         f[j] = max(f[j],f[j-v]+w);
    }
}

3  多重背包问题

N种物品和一个容量是V的背包。

第 种物品最多有件,每件体积是,价值是。

 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。

输出最大价值。

输入格式

第一行两个整数,NV,用空格隔开,分别表示物品种数和背包容积。

接下来有N行,每行三个整数,,用空格隔开,分别表示第 种物品的体积、价值和数量。

输出格式

输出一个整数,表示最大价值。

数据范围

0<N,V≤100

 文章来源地址https://www.toymoban.com/news/detail-781429.html

for(int i=1;i<=n;i++)
{
    cin>>a>>b>>c;
    for(int j=1;j<=c;j++)
    {
        v[cnt]=a;
        w[cnt]=b;
        cnt++;
    }//将多重背包一个一个拆出来,物品的重新叠加与整理 
}
for(int i=1;i<=cnt;i++)
{
    for(int j=m;j>=v[i];j--)
    {
        f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
}//01背包

优化:

int cnt = 0;     // 将物品重新分组后的顺序
for (int i = 1; i <= n; i ++)
{
     int a, b, s;    // a 体积, b 价值, s 每种物品的个数
     scanf("%d %d %d", &a, &b, &s);

     int k = 1;   // 二进制拆分 打包时每组中有 k 个同种物品
     while (k <= s)  // 即y总说的: 最后一组的物品个数 < 2^(n+1)   1 2 4 8 16 ... 2^n 2^(n+1)
     {
         cnt ++;
         v[cnt] = a * k;  // 每组的体积
         w[cnt] = b * k;  // 每组的价值
         s -= k;
         k *= 2;  // 注意是 k * 2,每次增长一倍,不是k * k
     }
     if (s > 0)   // 二进制拆分完之后 剩下的物品个数分为新的一组
     {
         cnt ++;
         v[cnt] = a * s;
         w[cnt] = b * s;
     }
}

4  分组背包问题

N组物品和一个容量是V的背包。

每组物品有若干个,同一组内的物品最多只能选一个。

每件物品的体积是,价值是,其中 是组号,是组内编号。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

输出最大价值。

输入格式

第一行有两个整数NV,用空格隔开,分别表示物品组数和背包容量。

接下来有N组数据:

·每组数据第一行有一个整数,表示第 个物品组的物品数量; 

·每组数据接下来有行,每行有两个整数,,用空格隔开,分别表示第 个物品组的第 个物品的体积和价值;

输出格式

输出一个整数,表示最大价值。

数据范围

0<N,V≤100

 

for(int i=0;i<n;i++)
{
    for(int j=m;j>=0;j--)
    {
        for(int k=0;k<s[i];k++)
        { 
             if(j>=v[i][k])     f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);  
        }
    }
}

到了这里,关于背包问题代码合集(C/C++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划:0-1背包、完全背包问题 | 详细原理解释 | 代码及优化(C++)

    目录 01背包 问题描述: 简单描述就是: 解析: 递推公式: dp数组的初始化: 遍历顺序: 图解: 实现代码: dp数组初始化: 遍历: 优化: 原理: 递推公式: 遍历顺序: 实现代码: 初始化: 遍历: 完全背包 问题描述: 解析: 实现代码:         01背包是在M件物品

    2024年02月11日
    浏览(36)
  • 【算法】算法学习七:动态规划 | 背包问题 | 最长公共子串(含源代码)

    背包问题是一种经典的组合优化问题,通常有两个版本:0-1背包问题和无限背包问题。 0-1背包问题是指给定一个背包容量和一组物品,每个物品有自己的重量和价值,要求在不超过背包容量的情况下,选择一些物品放入背包,使得物品的总价值最大化。每个物品只能选择放入

    2024年02月09日
    浏览(48)
  • 动态规划算法解决背包问题,算法分析与C语言代码实现,时间效率解析

    🎊【数据结构与算法】专题正在持续更新中,各种数据结构的创建原理与运用✨,经典算法的解析✨都在这儿,欢迎大家前往订阅本专题,获取更多详细信息哦🎏🎏🎏 🪔本系列专栏 -  数据结构与算法_勾栏听曲_0 🍻欢迎大家  🏹  点赞👍  评论📨  收藏⭐️ 📌个人主

    2023年04月16日
    浏览(50)
  • 【第二十五课】动态规划:完全背包问题(acwing-3 / 公式推导 / 思路理解 / 优化 / c++代码)

    目录 思路 朴素代码 优化 公式推导上  二维代码  一维代码 公式理解上   在开始看完全背包问题之前,可能需要先了解01背包及其解决办法。 指路👇 【第二十五课】动态规划:01背包问题(acwing-2 / 思路 / 含一维数组优化 / c++代码) 这个问题和01背包的区别就是 每件物品可以

    2024年03月19日
    浏览(63)
  • C++ 动态规划 01背包问题

    有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi ,价值是 wi 。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出最大价值。 输入格式 第一行两个整数, N,V ,用空格隔开,分别表示物品数量和背

    2024年04月27日
    浏览(40)
  • 算法系列--动态规划--背包问题(3)--完全背包介绍

    💕\\\"Su7\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(3)–完全背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(3)--完全背包介绍 链接: 完全背包 可以发现完全背包问题和01背包问题还是特比相似的 分析: 完全背包问题 是 01背包问题 的推广

    2024年04月25日
    浏览(44)
  • 算法系列--动态规划--背包问题(1)--01背包介绍

    💕\\\"趁着年轻,做一些比较cool的事情\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(1)–01背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(1)--01背包介绍 背包问题是动态规划中经典的一类问题,经常在笔试面试中出现,是非常 具有区分度 的题

    2024年04月16日
    浏览(55)
  • 动态规划——01背包问题(C++实现)

    整体思路: 利用动态规划,其目的就是将原问题分解成几个子问题,通过求解简单的子问题,把原问题给解决,就比如斐波那契数列方程: f[i]=f[i-1]+f[i-2]; 动态规划的核心就是找到原问题与子问题的关系,并列出动态转移方程。 实现方法: 这里我们可以定义一个二维数组,

    2024年02月11日
    浏览(55)
  • 【算法-动态规划】0-1 背包问题

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月08日
    浏览(46)
  • 算法学习17-动态规划01:背包问题

    提示:以下是本篇文章正文内容: 提示:这里对文章进行总结: 💕💕💕

    2024年04月27日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包