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

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

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

 

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

相关文章

【NOIP初赛 】哈夫曼树

【NOIP初赛 】哈夫曼树

根据我已刷的初赛题中基本每套的倒数第五或第六个不定项选择题就有一个关于哈夫曼树及其各种应用的题,占:0—1.5分;然而我针对这个类型的题也多次不会做,so,今晚好好研究下哈夫曼树;  概念:  给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二...

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

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

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

【已解决】ubuntu16.04和Python3.5里的大坑

因为一些历史原因,几个服务器的系统都一直是ubuntu16.04,ubuntu16.04的python3的默认版本是3.5。而我这次配置python环境需要用到Pymysql配置成功后,然后直接运行,一直报错。我还一直尝试修改pymysql的代码,一度以为镜像站里的pymysql有错误。甚至跑去Gi...

记录一次如何自己使用国外服务器搭建梯子

记录一次如何自己使用国外服务器搭建梯子

机缘巧合之下,租了一台亚马逊的美国服务器,想着这么大的服务器不能就跑一个业务吧,得利用起来,于是,就开始了搭建梯子之旅。 第一步:使用root账号登上ssh服务器。 第二步:执行一键搭建脚本: bash <(wget -qO- -o- https://git.io/v2ray.sh)...

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

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

发表评论

访客

看不清,换一张

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