您现在的位置是:首页 > 正文

用动态规划方法求解0-1背包问题

2024-04-01 06:47:21阅读 2

如果你对动态规划方法求解0-1背包问题的思路不清晰,直接阅读代码并不是一个好的建议。

推荐一个B站up主的视频讲解:
0/1背包问题-动态规划
练习地址(B站视频配套的网址)

#include<iostream>
using namespace std;

const int bagVolume = 6;//背包体积
const int itemNumber = 4;//准备放入的物品数量
const int rows = itemNumber + 1;//table表格的行:0,1,2,3,4  共5个数
const int cols = bagVolume + 1;//table表格的列:0,1,2,3,4,5,6   共7个数

void knapsack(int table[][cols], int weight[], int value[])
{
    
    int wt, vl;//wt是weight,vl是value
    for (int i = 1; i < rows; i++)
    {
        wt = weight[i-1];
        vl = value[i-1];
        for (int j = 1; j < cols; j++)
        {   
            /*           
            if (wt > j)//如果weight大于当前的背包容量j,
            {
                table[i][j] = table[i-1][j];//那么此物品放不进背包
            }
            else//如果weight小于当前的背包容量j,
            {   //那么,就判断(table[i-1][j-wt] + vl) 是不是大于 table[i-1][j]。如果大于,那么就table[i][j]=(table[i-1][j-wt] + vl);反之...
                table[i][j] = (table[i-1][j-wt] + vl) > table[i-1][j] ? (table[i-1][j-wt] + vl) : table[i-1][j];
            }
            */
            //简化写法
            table[i][j] = wt > j ?  table[i-1][j] : ((table[i-1][j-wt] + vl) > table[i-1][j] ? (table[i-1][j-wt] + vl) : table[i-1][j]);
        }
    }
    cout<<"动态规划表:"<<endl;
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            string str =  table[i][j] >= 10 ? "    " :  "     ";//如果是一位数就返回5个空格字符串,是两位数就返回4个空格字符串。
            cout<<table[i][j]<<str;
        }
        cout<<endl;
    }
    cout<<"放入背包的物品有:"<<endl;
    //打印放入背包的物品编号
    int j = bagVolume, sum_value=0;
    for (int i = itemNumber; i > 0; i--)
    {
        if (table[i][j] != table[i-1][j])
        {
            cout<<"【物品"<<i<<"】"<<endl;
            sum_value += value[i-1];
            j = j - weight[i-1];
        }
    }
    cout<<"背包中物品最大价值总和为:"<<sum_value<<endl;
}

int main()
{
    int table[rows][cols] = {0};
    int weight[itemNumber] = {2,2,4,2};
    int value[itemNumber] = {8,5,10,3};
    knapsack(table, weight, value);
    return 0;
}


网站文章

  • IOS Object和javaScript相互调用

    在IOS开发中有时会用到Object和javaScript相互调用,具体步骤如下:1. Object中执行javascript代码,这个比较简单,苹果提供了很好的方法- (NSString *)stringByEvaluatingJavaScriptFromString:(NSString *)script2. javascript执行过程中返回给Object的数据或者调用Obje

    2024-04-01 06:47:15
  • html的浮动作用是什么意思,html中浮动是什么

    html的浮动作用是什么意思,html中浮动是什么

    在HTML中,浮动就是让元素可以向左或向右移动,直到它的外边距碰到其父级的内边距或者是上一个元素的外边距,只需要给元素设置“float:left|right|none|inherit”样式即可。本教程操作环境:windows7系统、CSS3&&HTML5版、Dell G3电脑。一.什么是浮动(float)?浮动就是让元素可以向左或向右移动,直到它的外边距碰到其父级的内边距或者是上一...

    2024-04-01 06:46:33
  • 多线程&多进程

    一、线程&进程对于操作系统来说,一个任务就是一个进程(Process),比如打开一个浏览器就是启动一个浏览器进程,打开一个记事本就启动了一个记事本进程,打开两个记事本就启动了两个记事本进程,打开一个Word就启动了一个Word进程。进程是很多资源的集合(进程相当于是一个工厂)。·线程是包含在进程里面的,线程是用来运行干活的,线程就是最小的单位(相当于是工厂里面的工人)· 进程...

    2024-04-01 06:46:26
  • Silverlight/Windows8/WPF/WP7/HTML5周学习导读(7月2日-7月8日)

    Silverlight/Windows8/WPF/WP7/HTML5周学习导读(7月2日-7月8日)

    Silverlight/Windows8/WPF/WP7/HTML5周学习导读(7月2日-7月8日) 本周Silverlight学习资源更新 Silverlight之Window Phone 中SqlCE应用(17) zhaoyu_1979 Silverlight 4系列 +VS2010 + ArcGIS9.3 最短路径分析 wuwangrun

    2024-04-01 06:46:19
  • win10自带计算机应用恢复,win10重置电脑后怎么恢复应用_win10重置后恢复软件的方法...

    win10自带计算机应用恢复,win10重置电脑后怎么恢复应用_win10重置后恢复软件的方法...

    在使用win10操作系统的过程中,我们经常需要通过重置系统来解决一些问题,可是win10重置电脑后怎么恢复应用呢?有许多小伙伴不是很清楚该如何操作,所以对于这一情况,今天系统城小编为大家整理分享的就是...

    2024-04-01 06:46:11
  • Spring Cache 集成 Caffeine实现项目缓存

    Spring Cache 集成 Caffeine实现项目缓存

    一、前言 Spring Cache本身是Spring框架中一个缓存体系的抽象实现,本身不具备缓存能力,需要配合具体的缓存实现来完成,如Ehcache、Caffeine、Guava、Redis等。 二、...

    2024-04-01 06:45:28
  • cookie

    将不同的计算机通过网络应用使用对应的传输介质进行传输物理层、数据链路层、网络层、传输层、会话层、表示层、应用层[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7sSptn...

    2024-04-01 06:45:21
  • 魔兽正式服5区服务器互通信息,《魔兽世界》一区合并服务器正式通告

    为了迎接1.12版本中的跨服务器战场功能,并进一步提升服务器表现以满足用户的需求,我们将对现有服务器的架构进行调整,一区至五区的服务器将进行小规模的服务器合并操作。我们已经从今天凌晨5点开始,对一区的...

    2024-04-01 06:45:14
  • 15HD_OJ——Tian Ji -- The Horse Racing

    15HD_OJ——Tian Ji -- The Horse Racing

    /* * Copyright (c) 2014, 烟台大学计算机学院 * All rights reserved. * 文件名称:test.cpp * 作 者:李晓凯 * 完成日期:2015年 6 月 11 日 * 版 本 号:v1.0 * * 问题描述: * 输入描述: * 程序输出: */ Problem Descriptio

    2024-04-01 06:44:35
  • react 表格高度自适应

    使用calc()给元素的border、margin、pading、font-size和width等属性设置动态值。不过calc()最大的好处就是用在流体布局上,可以通过calc()计算得到元素的宽度。...

    2024-04-01 06:44:19