蛮力法解决01背包问题-程序员宅基地

技术标签： 数据结构与算法  

蛮力法：设计算法求解背包问题，并编程实现。

背包问题: 

给定重量分别为,价值分别为的n件物品，和一个承重为W的背包。求这些物品中一个最有价值的子集，并能装到背包中。

背包问题的蛮力解法是穷举这些物品的所有子集，找出能够装到背包中的所有子集，并在这些子集中找出价值最大的子集。

实验：

编写程序，实现背包问题的蛮力算法。并针对以下两个实例，求出能装到背包中的价值最大的子集。要求输出：最优可行子集和该子集的最大价值。

代码实现：

#include <iostream>

int sum_v;//货物总价值
int sum_w;//货物总重量
int goodNum;//一共有多少货物
int ans;//背包中现有几个货物
int maxWeight;//背包的总容量
int r[100];//记录最后的选择的货物标号

using namespace std;
struct good
{
    int weight;
    int value;
    int flag;//记录该货物是否被挑选
}goods[100];
//更新序列，并返回最大
int record(int sum_v)
{
    int count_good = 0;
    r[0] = sum_v;
    for(int i = 1;i <= goodNum;i++)
    {
        if(goods[i].flag == 1)
        {
            r[++count_good] = i;
        }
    }
    return count_good;
}
void findMin(int x)
{
    if(sum_w > maxWeight)
    {
        return;
    }
    //最好在此处判断sun_v是否为最大，这样才不会有sum_w > maxWeight的情况
    if(sum_v > r[0])
    {
        ans = record(sum_v);
    }
    //注意此处循环的条件
    for(int i = x;i < goodNum;i++)
    {
        sum_w += goods[i].weight;
        sum_v += goods[i].value;
        goods[i].flag = 1;
        findMin(i + 1);
        sum_w -= goods[i].weight;
        sum_v -= goods[i].value;
        goods[i].flag = 0;
    }
}

int main()
{
    cin >> goodNum >> maxWeight;
    for(int i = 1;i <= goodNum;i++)
    {
        goods[i].flag = 0;
        cin >> goods[i].weight >> goods[i].value;
    }
    findMin(0);
    for(int i = 1;i <= ans;i++)
    {
        cout << r[i] << " ";
    }
    cout << "maxValue" << r[0] << endl;
    return 0;
}

第一行输入货物总个数和背包的总容量

10 60
23 20
15 14
8 7
20 18
7 5
10 11
9 10
16 15
21 19
13 12
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/Geek_sun/article/details/82848705

智能推荐

计算机系统：微处理器详解，全面剖析！-程序员宅基地

文章浏览阅读599次。本文对计算机系统中的微处理器进行了全面剖析。首先介绍了微处理器的基本原理，包括控制单元、算术逻辑单元和寄存器组等组成部分。接着详细阐述了微处理器的工作方式，包括指令周期和执行周期。然后回顾了微处理器的发展历程，从Intel 4004到多核时代的演进。最后展望了微处理器的未来趋势，包括并行计算、异构计算以及能效提升的挑战。通过全面了解微处理器，读者可以更好地理解计算机系统的运作原理，并为未来的发展做好准备。_微处理器

SSA-CNN-BIGRU基于麻雀算法优化卷积神经网络-双向门控循环单元SSA-CNN-BIGRU分类预测_ssa优化bigru-程序员宅基地

文章浏览阅读64次。SSA-CNN-BIGRU基于麻雀算法优化卷积神经网络-双向门控循环单元SSA-CNN-BIGRU分类预测_ssa优化bigru

《手把手教你》系列技巧篇（三十一）-java+ selenium自动化测试- Actions的相关操作-番外篇（详解教程）-程序员宅基地

文章浏览阅读813次，点赞19次，收藏25次。上一篇中，宏哥说的宏哥在最后提到网站的反爬虫机制，那么宏哥在自己本地做一个网页，没有那个反爬虫的机制，谷歌浏览器是不是就可以验证成功了，宏哥就想验证一下自己想法，于是写了这一篇文章，另外也是相对前边做一个简单的总结分享给小伙伴们或者童鞋们。废话不多数，直接进入今天的主题。

Linux系统Shell编程及自动化运维实现-判断_linux shell编程和自动化运维-程序员宅基地

文章浏览阅读155次。Linux Shell编程及自动化运维实现-判断一.shell条件测试1.1格式1.2文件测试[ 操作符 文件或目录 ]1.3数值比较[ 整数1 操作符 整数2 ]1.4字符串比较[ "字符串" = "字符串" ]1.5and和or二.流程控制：if1.单分支结构2.双分支结构3多分支结构4.嵌套结构三.模式匹配：case1.case语法结构2.简单的模式匹配3.简单的jumpserver4.系统管理工具箱四.小结一.shell条件测试1.1格式格式1：test 条件表达式格式2：[ 条件表达_linux shell编程和自动化运维

hue——hbase、hive的使用_hue 端口-程序员宅基地

文章浏览阅读8.9k次，点赞6次，收藏18次。hue入口：http://hue服务器地址:8888/about/hue默认端口号8888账号：xxxx密码：xxxxhue作用，提供给大数据用户一个web端，访问大数据集群1、 hbase web端的使用l hbase hue入口如图，data browsers选项中会有hbase选项，直接点进去就好 l 点进来后会看到我们集群hbase中的所有..._hue 端口

JMeter Ramp-up 说明-程序员宅基地

文章浏览阅读1.1w次，点赞4次，收藏28次。Ramp-up Period（in seconds）【1】决定多长时间启动所有线程。如果使用10个线程，ramp-up period是100秒，那么JMeter用100秒使所有10个线程启动并运行。每个线程会在上一个线程启动后10秒（100/10）启动。Ramp-up需要要充足长以避免在启动测试时有一个太大的工作负载，并且要充足小以至于最后一个线程在第一个完成前启动。 一般设置ramp-up=线程数启动，并上下调整到所需的。【2】用于告知JMeter 要在多长时间内建立全部的线程。默认值是0。如果._jmeter ramp-up

随便推点

Windows网络编程-I/O模式_win io写程序-程序员宅基地

文章浏览阅读367次。首先说明什么是Windows套接字模式.其分为两类:阻塞模式/非阻塞模式.阻塞模式:I/O操作完成前执行操作的WinSock调用会一直等候下去,不会立即返回到程序中.非阻塞模式:WinSock函数无论如何都会立即返回.对阻塞套接字他的一个缺点在于,应用程序很难同时通过多个建好连接的套接字通信,使用前述的方案,可对应用程序进行修改,令其为连接好的每个套接字都分配一个读线程,以及一个数据处理..._win io写程序

R语言_ggplot2_r中ggplot2-程序员宅基地

文章浏览阅读128次。【代码】ggplot2作图_一些基本参数。_r中ggplot2

视频转图片工具-程序员宅基地

文章浏览阅读593次。将单个视频转成图片参数-i: 视频文件地址-o: 图片输出文件夹地址-f: 抽取帧数跨步代码核心就是cv2模块，先cv2.VideoCapture读取视频，然后通过cv对象的read()来获取每一个视频画面帧，进行进行存储等操作。#!/usr/bin/env python# -*- coding:utf-8 -*-import cv2import osimport argparseimport globimport timefrom common import init_lo_视频转图片工具

1024程序员节：谈谈自我感受_程序员节 谷歌-程序员宅基地

文章浏览阅读1.2k次，点赞3次，收藏2次。应 ：1024程序员节 | 全民狂欢，拒绝加班的一条博客前文：写这篇博客的时候，正在加班，在北京，如果没猜错的话明天周日也会加。不知道现在的你们是否也和我一样正在像这些邪恶势力低头，默默的加班。我相信有，一定有。刚开始接触编程，大概是在初中，完全是因为兴趣，没想过它会真正的成为我生活中的一部分，要知道当你的兴趣爱好成为你的第一职业并支撑你生活的时候，你就会对它产生厌恶感，我不知道你们是不是这样，但拿我个人来说，我就是这样。从最开始玩vbs脚本，到后来偶然接触js脚本，从刚开始的一个小白到后来真正踏入编_程序员节 谷歌

vue-Cli3，Vue-Cli4打包后如何配置静态资源路径？（自定义浏览器icon图标，title文本）_vue 打包后固定域名运行静态资源-程序员宅基地

文章浏览阅读3k次，点赞3次，收藏2次。文章目录为什么要配置静态资源路径？1、首先我们要清楚什么样的环境下我们需要配置静态资源路径？2、如何配置？为什么要配置静态资源路径？1、首先我们要清楚什么样的环境下我们需要配置静态资源路径？那肯定是不是单纯的一个前端写的单页面应用的时候，我们仔细想想，如果我们开发了一个新模块，但是不是基于原来项目开发的，而实更换了一个路径？不不不，只是说新起了一个子路径，相当于二级路径，那么这个时候我们还能用原来的默认的配置去寻找接口地址，静态资源地址吗？当然这样肯定是行不通的，所以说我们需要配置一下你当前这个模块_vue 打包后固定域名运行静态资源

apollo学习之---planning理论到实践（6）坐标变换代码学习_apollo坐标转换-程序员宅基地

文章浏览阅读696次。文章目录step1step2step3step4step5piecewise_jerk_path_optimizer.ccstep1 const auto init_frenet_state = reference_line.ToFrenetFrame(planning_start_point); //===>step2step2std::pair<std::array<double, 3>, std::arr_apollo坐标转换

推荐文章

热门文章

相关标签