Mrhanice

背包问题

codeforces(2) DP基础(3) POJ(8) UVA(14) 云服务器(1) 区间DP(4) 图论(2) 扩展欧几里得(1) 杂谈(2) 树状数组(1) 状态压缩DP(1) 状态空间搜索(1) 简单水题(3) 线段树(4)

/ 注册

全部文章 / 背包问题（共3篇）

SuperSale UVA - 10130

01背包题目描述：一家人去超市买东西，各种物品有价格和重量，每个人都有自己的背包容量，求这一家人能够获得最大价值。解题分析：刚开始被这题给唬住了，想成了如果一个物品被某人买了，则其他人不可以卖这个物品，那这就难了。但是想想也该明白那家超市一种物品只卖一件啊，超时的物品是任意多的。...

2017-08-10

0 653

The trouble of Xiaoqian HDU - 3591

多重背包 + 完全背包题目描述：xiaoqian需要买T钱的货物，他有n种不同面值的硬币，每种硬币是有限个。他给收银员钱，收银员找给他钱（如果需要找钱的话），收银员总是给他最少的硬币数目。求xianqian最少需要接触多少硬币（他给收银员的，收银员给他的）。解题分析：可以分别计算...

2017-08-07

0 563

Piggy-Bank HDU - 1114

完全背包题目描述：有一个小猪存钱罐，求在正好的重量的情况下的，存钱的最小值，如果不能满重输出This is impossible. 解题分析：不限次数，完全背包，因为是求最小值，所以初始化时是满重，但是dp[0]必须得是0，不然dp[j] = min (dp[j], dp[j-w[...

2017-08-04

0 452