Codeforces Round #365 (Div. 2) E - Mishka and Divisors（转化成01-背包）
http://codeforces.com/contest/703/problem/E题意：给出n个数和一个k，计算出至少要多少个数相乘才是k的倍数。思路：这道题目参考了杭电大神的代码http://blog.csdn.net/snowy_smile/article/details/52134304。...
UVA 562 Dividing coins --01背包的变形
01背包的变形。先算出硬币面值的总和，然后此题变成求背包容量为V=sum/2时，能装的最多的硬币，然后将剩余的面值和它相减取一个绝对值就是最小的差值。代码：#include <iostream>#include <cstdio>#include <cstring>...
01背包 URAL 1073 Square Country
题目传送门 /* 题意：问n最少能是几个数的平方和 01背包：j*j的土地买不买的问题 详细解释：http://www.cnblogs.com/vongang/archive/2011/10/07/2200721.html */ #include <cstdio>...
POJ3628 Bookshelf 2(01背包+dfs)
Bookshelf 2Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 8745 Accepted: 3974DescriptionFarmer John recently bought another bookshelf for t...
POJ 3628 Bookshelf 2（01背包）
Bookshelf 2Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 9488 Accepted: 4311DescriptionFarmer John recently bought another bookshelf for t...
【洛谷】【动态规划/01背包】P1734 最大约数和
【题目描述：】选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。【输入格式：】输入一个正整数S。【输出格式：】输出最大的约数之和。[算法分析：]01背包，每个数的约数和为其价值，数的大小为其花费注意1的价值应该为0[Code:]#include<iostream>...
HDU 2955（01背包问题）
M - 01背包Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64uDescriptionThe aspiring Roy the Robber has seen a lot of Ameri...
HDU 2639 骨头收集者 II【01背包 】+【第K优决策】
题目链接：https://vjudge.net/contest/103424#problem/H题目大意：与01背包模板题类似，只不过要我们求第K个最大的总价值。解题分析：其基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。这里仍然以01背包为例讲解一下。首...
01背包问题（Java实现）
关于背包问题，百度文库上有崔添翼大神的《背包九讲》，不明的请移步查看。这里仅介绍最基本的01背包问题的实现。 public class Knapsack { private final int MIN = Integer.MIN_VALUE; @org.junit.Test ...
HDU 2191（多重背包转换为01背包来做）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2191悼念512汶川大地震遇难同胞——珍惜现在，感恩生活Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Jav...
hdu 3339 In Action (最短路径+01背包)
In ActionTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3869 Accepted Submission(s): 1237P...
codeforce Gym 101102A Coins （01背包变形）
01背包变形，注意dp过程的时候就需要取膜，否则会出错。代码如下：#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define MAXW 15005#define N ...
POJ 3211 Washing Cloths(01背包变形)
Q: 01背包最后返回什么 dp[v], v 是多少?A: 普通01背包需要遍历, 从大到小. 但此题因为物品的总重量必定大于背包容量, 所以直接返回 dp[V] 即可update 2014年3月14日11:22:551. 几个月后, 感觉返回的不应该是 dp[V], 二是 dp[0...V] 中的...
【01背包变形】Robberies HDU 2955
http://acm.hdu.edu.cn/showproblem.php?pid=2955【题意】有一个强盗要去几个银行偷盗，他既想多抢点钱，又想尽量不被抓到。已知各个银行的金钱数和被抓的概率，以及强盗能容忍的最大被抓概率。求他最多能偷到多少钱？【思路】01背包：每个物品代价是每个银行钱的数目，物...
FZU 2214 Knapsack problem 01背包变形
题目链接：Knapsack problem大意：给出T组测试数据，每组给出n个物品和最大容量w.然后依次给出n个物品的价值和体积。问，最多能盛的物品价值和是多少？思路：01背包变形，因为w太大，转而以v为下标，求出价值对应的最小体积，然后求出能够满足给出体积的最大价值。经典题目，思路倒是挺简单的，就...
CF#214 C. Dima and Salad 01背包变形
C. Dima and Salad题意有n种水果，第i个水果有一个美味度ai和能量值bi,现在要选择部分水果做沙拉，假如此时选择了m个水果，要保证\(\frac{\sum_{i=1}^ma_i}{\sum_{i=1}^mb_i}==k\)，问沙拉最大的美味度是多少？思路01背包变形。对于给出的公式，...
[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...
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 ...