背包问题 (DP)
利用记忆化数组.记dp[i][j]为根据rec的定义,从第i个物品开始挑选总重小于j时,总价值的最大值.递推式:dp[i][j]=0 (j<w[i])dp[i][j]dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])反向: int dp[MAX]...
vijos1334 NASA的食物计划（二维费用的背包问题）
背景NASA(美国航空航天局)因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋,因此在各方压力下终止了航天飞机的历史,但是此类事情会不会在以后发生，谁也无法保证,在遇到这类航天问题时,解决方法也许只能让航天员出仓维修,但是多次的维修会消耗航天员大量的能量,因此NASA便想设计一种食品方案,让体积和...
[Jsoi2016]最佳团体 BZOJ4753 01分数规划+树形背包/dfs序
分析：化简一下我们可以发现，suma*ans=sumb，那么我们考虑二分ans，之后做树形背包上做剪枝。时间复杂度证明，By GXZlegend O（nklogans）附上代码：#include <cstdio>#include <algorithm>#include <...
POJ1976A Mini Locomotive(01背包装+连续线段长度）
A Mini LocomotiveTime Limit: 1000MS Memory Limit: 30000KTotal Submissions: 2485 Accepted: 1388DescriptionA train has a locomotive that pulls the train...
完全背包变型题（hdu5410)
这是2015年最后一场多校的dp题，当时只怪自己基础太差，想了1个多小时才想出来，哎，9月份好好巩固基础，为区域赛做准备。题目传送门题目的意思是给你n元钱，m类糖果，每类糖果分别有p, a, b, p表示单价，假设付了w*p元，那么他能获得a*w + b个糖果。求最大的糖果数。当时一看到这题，觉得是...
dp 二维乃至多维背包
洛谷P1855 榨取kkksc03分析：套路是很明显的01背包，但是这时受约束的变量有两个了，这种情况下就该用多维背包了分析方法一样的，用dp[i][j][k]表示从前i个愿望中挑选总时间和总金钱不超过j,k时的最大愿望数。则状态转移方程应该为：dp[i][j][k]=max(dp[i-1][j][...
hdu2159完全背包
md心里有事的时候不能写题操FATETime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 13285 Accepted Submission...
iOS 学习 - 20 UICollectionView 移动 Item ，类似背包
有100个 item，数据源只有20个，只能在 20 个之间移动，防止 item 复用，出现 bug方法一：苹果自带//UICollectionViewDataSource- (BOOL)collectionView:(UICollectionView *)collectionView canMov...
HDU 2639 Bone Collector II(01背包变形【第K大最优解】)
Bone Collector IITime Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4739 Accepted Submission(...
Temple Build~dp（01背包的变形）
The Dwarves of Middle Earth are renowned for their delving and smithy ability, but they are also master builders. During the time of the dragons, the ...
P1757 通天之分组背包
P1757 通天之分组背包背包中的经典问题，我竟然不知道。分组背包就是每个物品有一个所属的小组，小组内的物品会冲突。就是把01背包中的两个for换一下位置01：for(i，1，kind) for(j,v,w[i])分组背包 for(j,v,w[i]) for(i，1，kind) #incl...
POJ 3628 Bookshelf 2【01背包】
题意：给出n头牛的身高，以及一个书架的高度，问怎样选取牛，使得它们的高的和超过书架的高度最小。将背包容量转化为所有牛的身高之和，就可以用01背包来做=== #include<iostream> #include<cstdio> #include<cstring> ...
洛谷 P1064 金明的预算方案 (有依赖的0/1背包)
题目描述金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过NN元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些...
[DP之多重背包优化方法]
首先我们看一道有趣的题目然后这道题很快想到是一个多重背包和无限背包混合体那么我们就以这道题 来讨论一下多重背包的优化首先我们看看朴素打法memset(F,,sizeof(F)); F[]=; for(int i=;i<=N;i++) for(int k=;k<=C[i];k++...
C - Coin Change (III)（多重背包 二进制优化）
C - Coin Change (III)Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %lluSubmit Status Practice LightOJ 1233DescriptionIn a ...
POJ 1014 Dividing(多重背包, 倍增优化)
Q: 倍增优化后, 还是有重复的元素, 怎么办A: 假定重复的元素比较少, 不用考虑DescriptionMarsha and Bill own a collection of marbles. They want to split the collection among themselves s...
51Nod 1007 正整数分组 | DP （01背包）
Input示例512345Output示例1分析：2组的差最小，那么每一组都要接近sum/2,这样就转化成了普通的0 - 1背包了#include <bits/stdc++.h>using namespace std;typedef long long LL;#define rep(i,...
51Nod 1007 正整数分组（01背包）
将一堆正整数分为2组，要求2组的和相差最小。例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。Input第1行：一个数N，N为正整数的数量。第2 - N+1行，N个正整数。(N <= 100, 所有正整数的和 <= 10000)Outp...
HDU 2602 Bone Collector (01背包DP)
题意：给定一个体积，和一些物品的价值和体积，问你最大的价值。析：最基础的01背包，dp[i] 表示体积 i 时最大价值。代码如下：#pragma comment(linker, "/STACK:1024000000,1024000000")#include <cstdio>#includ...
hdoj 2602 Bone Collector 【01背包】
意甲冠军：给出的数量和袋骨骼的数，然后给每块骨骼的价格值和音量。寻求袋最多可容纳骨骼价格值难度;这个问题是最基本的01背包称号，不知道的话，推荐看《背包9说话》AC by SWS主题链接 http://acm.hdu.edu.cn/showproblem.php?pid=2602代码：#includ...