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

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

virtualman8年前 (2017-10-02)默认分类1202

 

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

相关文章

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

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

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

【已解决】Window命令行报错:无法加载文件,因为在此系统上禁止运行脚本。

错误:无法加载文件 D:\Program Files\nodejs\tsc.ps1,因为在此系统上禁止运行脚本。有关详细信息,请参阅 https:/go.microsoft.com/fwlink/?LinkID=135170 中的 about_Execution_Policies。 解决方法:...

大佬推荐用的两个git指令:git rebase 和 git commit --amend

git rebase git rebase 命令用于将本地的提交重新应用到另一个基础分支上。它可以帮助你保持线性的项目历史记录,避免大量的合并提交(merge commits)。当你从一个分支拉取最新的更改并希望将你的工作基于这些更改之上时,可以使用 git rebase。 使用场景: 当...

常见License代码开源要求

  常见许可证类型 典型软件 触发代码开源义务前提要求 开源要求和范围 BSD类 如:Apache/BSD/MIT等 Tomcat;OpenSSL 无 无 MPL类 如:MPL/EPL等 FirFox,Eclips...

解决!!!关于微信小程序中无法正常显示uview-plus的up-tabs组件样式的问题

解决!!!关于微信小程序中无法正常显示uview-plus的up-tabs组件样式的问题

一.问题背景uview-plus3.0是基于uView2.x修改的vue3版本,提供了很多好用的移动端组件。点击访问最近在使用uview-plus的tabs标签组件时,需要对标签的背景颜色等样式进行自定义,查看官方文档发现提供了参数activeStyle、inactiveStyle、itemStyl...

【随笔】关于开发一个既能日常记账,又能拥有资产管理功能的APP的Idea

随便写了,想到哪里写哪里。最近一直在市面找一款记账APP,但是感觉都不满足我的需求。我的想法是,在普通账本程序的基础上,再加上多人管理。资产管理。资产管理一定要把价格接口对接好。我举个例子,比如有虚拟货币资产ETH 1个,那么就应该在统计的时候,按实时市值进行统计。又或者按照当天的市值统计。关于资产...

发表评论

访客

看不清,换一张

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