当前位置:首页 > 默认分类 > 正文内容

【动态规划】基础背包问题

virtualman7年前 (2017-10-02)默认分类61

 

1159. 背包问题一 (Standard IO)

时间限制: 1000 ms  空间限制: 262144 KB  具体限制  

题目描述

有个背包可承受重量N,现有T件物品
每件物品重量为Wi,价值为Vi ,每件物品只有一个,这个背包可以装载物品的最大价值是多少?

输入

一行,N T 之间用空格隔开。
后面t行,每行:重量Wi,价值Vi。

输出

这个背包可以装载物品的最大价值。

样例输入

100 5

77 92

22 22

29 87

50 46

99 90

样例输出

133

数据范围限制

N<=1000,T<=100,1<=Wi,Vi<=100

/*
问题:
有个背包可承受重量N,现有T件物品.
每件物品重量为Wi,价值为Vi.
每件物品只有一个.
这个背包可以装载物品的最大价值是多少?
*/
#include <iostream>
#include <cstdio>
using namespace std;
//定义三个数组, W为不同物体的 重量,V为不同物体的价值,F为不同称量背包的总价值; 
int W[2005],V[2005],F[2005];
int main()
{
    /*-------定义变量并读入数据------------*/
    int N,T;
    scanf("%d %d",&N,&T);
    for(int i=1;i<=T;i++)
        scanf("%d %d",&W[i],&V[i]);
    /*--------------动态规划----------------*/
    for(int i=1;i<=T;i++)//遍历每一件物品 
        for(int j=N;j>=W[i];j--)//不断地尝试 放置每一件物品 
        {
            F[j]=max(F[j-W[i]]+V[i],F[j]);//状态转移方程: F[j]=max(F[j-W[i]]+V[i],F[j])   刷新最大背包的当前最大价值; 
            /*详细分析此处:
            这里使用了动态规划算法,其实也就是记忆化搜索,
            就是把F【】中没搜一次都记录在F这个数组中,
            以后再次递归或递推时,就不需要 再次的计算,
            直接从数组中查询是否存在,如果存在,直接调用即可; 
            */
        }
    /*----------------输出解答-------------*/
    cout<<F[N]<<endl;
    return 0;    
} //PS:2017年10月2日19:02:02

相关文章

【Socket通信】关于Socket通信原理解析及python实现

【Socket通信】关于Socket通信原理解析及python实现

Socket(套接字)通信{网络通信其实就是Socket间的通信},首先了解下概念:【来源于百度百科】1"两个程序通过一个双向的通信连接实现数据的交换,这个连接的一端称为一个socket。"可以这么说,Socket就是一个网络编程的接口(API),它定义了一种标准,并对TCP/I...

python实现对简单的运算型验证码的识别【不使用OpenCV】

python实现对简单的运算型验证码的识别【不使用OpenCV】

最近在写我们学校的教务系统的手机版,在前端用户执行绑定操作后,服务器将执行登录,但在登录过程中,教务系统中有个运算型的验证码,大致是这个样子的: 下面我们开始实现这个验证码的识别。1、图片读取从网站上下载大量同类型的验证码,人工标记上每个验证码的识别结果2、图片灰度化、二值化灰度化,在RGB模型中...

【vue】vue3实现表格(JSON)数据导出Excel

【vue】vue3实现表格(JSON)数据导出Excel

首先安装xlsx依赖npm install xlsx --save项目中引入import * as XLSX from "xlsx";此方法纯导出数据,没有其他设置,对导出的Excel表格没有要求时可...

跑在内存中的数据库——H2数据库

跑在内存中的数据库——H2数据库

今天接触到了一个非常有意思的数据库,叫H2数据库。在众多数据库中,H2数据库以其独特的特性——内存数据库模式,吸引了大量开发者的关注。今天,就来深入探讨一下这个跑在内存中的数据库——H2数据库。 一、H2数据库简介 H2是一个轻量级的关系型数据库,它支持嵌入式和客户...

【PHP】大量 HTTP 请求调第三方接口,接口堵塞引起的 FD 耗尽(too many file open)问题

“FD耗尽”中的“FD”指的是“文件描述符”(File Descriptor)。在Unix和类Unix系统(如Linux)中,文件描述符是一个非负整数,用于标识一个进程打开的文件或其他输入/输出资源,比如网络套接字(socket...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。