题目链接:poj 3624
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。
用子问题定义状态:即F [i, v]表示前i件物品恰放入一个容量为v 的背包可以
获得的最大价值。则其状态转移方程便是:
F [i, v] = max{F [i − 1, v], F [i − 1, v − Ci ] + Wi }
这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生
出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v 的背包
中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化
为一个只和前i − 1件物品相关的问题。如果不放第i件物品,那么问题就转化
为“前i − 1件物品放入容量为v 的背包中”,价值为F [i − 1, v];如果放第i件物
品,那么问题就转化为“前i − 1件物品放入剩下的容量为v − Ci 的背包中”,
此时能获得的最大价值就是F [i − 1, v − Ci ]再加上通过放入第i件物品获得的价
值 Wi 。
伪代码如下:
F [0, 0..V ] = 0
for i = 1 to N
for v = Ci to V
F [i, v] = max{F [i − 1, v], F [i − 1, v − Ci ] + Wi }
以上方法的时间和空间复杂度均为O(V N ),其中时间复杂度应该已经不能
再优化了,但空间复杂度却可以优化到O(V )。
先考虑上面讲的基本思路如何实现,肯定是有一个主循环i = 1..N ,每次
算出来二维数组F [i, 0..V ]的所有值。那么,如果只用一个数组F [0..V ],能不
能保证第i次循环结束后F [v]中表示的就是我们定义的状态F [i, v]呢?F [i, v]是
由F [i − 1, v]和F [i − 1, v − Ci ]两个子问题递推而来,能否保证在推F [i, v]时(也
即在第i次主循环中推F [v]时)能够取用F [i − 1, v]和F [i − 1, v − Ci ]的值呢?事
实上,这要求在每次主循环中我们以v = V..0的递减顺序计算F [v],这样才能保
证推F [v]时F [v − Ci ]保存的是状态F [i − 1, v − Ci] 的值。伪代码如下:
F [0..V ] = 0
for i = 1 to N
for v = V to Ci
F [v] = max{F [v], F [v − Ci ] + Wi }
其中的F [v] = max{F [v], F [v − Ci ] + Wi }一句,恰就对应于我们原来的转移方
程,因为现在的F [v − Ci ]就相当于原来的F [i − 1, v − Ci ]。如果将v 的循环顺序
从上面的逆序改成顺序的话,那么则成了F [i, v]由F [i, v − Ci ]推导得到,与本题
意不符。
代码:
#include<stdio.h>
#include<iostream>
#include<string.h>
#define N 3405
using namespace std;
int bag[12900];
int w[N],d[N];
int main(void)
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>w[i]>>d[i];
memset(bag,0,sizeof(bag));
for(int i=1;i<=n;i++)
for(int k=m;k>=w[i];k--)
{
if(bag[k-w[i]] + d[i] > bag[k])
bag[k] = bag[k - w[i]] + d[i];
}
cout<<bag[m]<<endl;
return 0;
}
poj 3624 Charm Bracelet 01背包问题的更多相关文章
-
POJ 3624 Charm Bracelet(01背包裸题)
Charm Bracelet Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 38909 Accepted: 16862 ...
-
POJ 3624 Charm Bracelet(01背包)
Charm Bracelet Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 34532 Accepted: 15301 ...
-
POJ 3624 Charm Bracelet(01背包模板题)
题目链接 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 52318 Accepted: 21912 Descriptio ...
-
POJ 3624 Charm Bracelet 0-1背包
传送门:http://poj.org/problem?id=3624 题目大意:XXX去珠宝店,她需要N件首饰,能带的首饰总重量不超过M,要求不超过M的情况下,使首饰的魔力值(D)最大. 0-1背包入 ...
-
POJ.3624 Charm Bracelet(DP 01背包)
POJ.3624 Charm Bracelet(DP 01背包) 题意分析 裸01背包 代码总览 #include <iostream> #include <cstdio> # ...
-
POJ 3624 Charm Bracelet (01背包)
题目链接:http://poj.org/problem?id=3624 Bessie has gone to the mall's jewelry store and spies a charm br ...
-
POJ 3624 Charm Bracelet(01背包模板)
Charm Bracelet Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 45191 Accepted: 19318 ...
-
poj 3624 Charm Bracelet(01背包)
Charm Bracelet Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 29295 Accepted: 13143 ...
-
[再做01背包] POJ 3624 Charm Bracelet
接触动态规划的第一题是数塔问题,第二题就是01背包问题了. 当时看的懵懵懂懂,回过头来再看这道题还是非常简单的了. 用 dp[i][j] 表示取前i种物品,使它们总体积不超过j的最优取法取得的价值总和 ...
随机推荐
-
Python~recursive function递归函数
尾递归实现循环 def fact(n): if n==1: return 1 else : return n * fact(n-1) raw_input() 字符而非数字 unsupported op ...
-
STMFD 和LDMFD指令
http://blog.163.com/oy_mcu/blog/static/16864297220120193458892/ LDM/STM指令主要用于现场保护,数据复制,参数传送等. STMFD指 ...
-
atan函数与atan2函数
atan函数:传送门. atan2函数:传送门. atan 和 atan2 都是求反正切函数,如:有两个点 point(x1,y1), 和 point(x2,y2); 那么这两个点形成的斜率的角度计算 ...
-
Spring MVC笔记 使用JdbcTemplate
Spring提供了 JdbcTemplate 来封装数据库jdbc操作细节, 包括: 数据库连接[打开/关闭] ,异常转义 ,SQL执行 ,查询结果的转换, 其中体现了 模板模式 的设计模式思想. 使 ...
-
Workspace in use or cannot be created, choose a different one.--错误解决办法
eclipse 使用一段时间后,有时会因为一些故障自己就莫名奇妙的关闭了,再打开时有时没有问题,有时有会提示错误 Workspace Unavailable: 原因:出现这种情况一般是workspac ...
-
Google Code Jam 第一题
通过的第一题,留做纪念,呵呵,非常简单,Africa 2010, Qualification Round: Store Credit. #include <stdio.h> #includ ...
-
菜鸟玩云计算之十六:Ubuntu14.04上创建的虚拟机迁移到RHEL6.4
菜鸟玩云计算之十六:Ubuntu14.04上创建的RHEL6.4虚拟机迁移到RHEL6.4主机上 RHEL6.4 Server作为虚拟机的HOST,执行以下的命令检查配置和安装相关软件: # egre ...
-
poj2912 Rochambeau
Description N children are playing Rochambeau (scissors-rock-cloth) game with you. One of them is th ...
-
Linux下安装软件命令详解
---------------------------------------------------------------- 或许你对于linux还不够了解,但是一旦你步入公司后,你就会发现lin ...
-
由time.tzname返回值引发的对str、bytes转换时编码问题实践
Windows 10家庭中文版,Python 3.6.4, 下午复习了一下time模块,熟悉一下其中的各种时间格式的转换:时间戳浮点数.struct_tm.字符串,还算顺利. 可是,测试其中的time ...