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背包为例讲解一下。首...
【bzoj5018】[Snoi2017]英雄联盟 背包dp
题目描述正在上大学的小皮球热爱英雄联盟这款游戏，而且打的很菜，被网友们戏称为「小学生」。现在，小皮球终于受不了网友们的嘲讽，决定变强了，他变强的方法就是：买皮肤！小皮球只会玩N个英雄，因此，他也只准备给这N个英雄买皮肤，并且决定，以后只玩有皮肤的英雄。这N个英雄中，第i个英雄有Ki款皮肤，价格是每款...
HDU 5501 背包问题
需要按照B/C的值从大到小排序。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#include<queue&g...
POJ 3093 Margaritas(Kind of wine) on the River Walk (背包方案统计)
题目DescriptionOne of the more popular activities in San Antonio is to enjoy margaritas in the park along the river know as the River Walk. Margaritas m...
bzoj 1531 Bank notes 多重背包/单调队列
多重背包二进制优化终于写了一次，注意j的边界条件啊，疯狂RE(还是自己太菜了啊啊)最辣的辣鸡#include<bits/stdc++.h>using namespace std;int n,sum;const int N=;const int C=;const int K=;const ...
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 5677 ztr loves substring 多重背包
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 178 Accepted Submission(s): 93Problem Descr...
dd大牛的《背包九讲》
P01: 01背包问题 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本思路 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即f[i][v]表示前i...
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...
多重背包之 HDU -1171Big Event in HDU &HDU -2191悼念512汶川大地震遇难同胞——珍惜现在，感恩生活
这两道题都是多重背包的基础题，前面的安格题意是:给出每个物体的价值和物体的数量，如何分使得A,B所得价值最接近并且A的价值不能小于B,就类似于NYOJ上的那个邮票分你一半那个意思,只不过这里不是一个而是多个，所以多重背包前一个题是将总和的一半当作背包的容量来求，代码如下 #include <i...
HDU 1114 iggy-Bank(完全背包)
水给出小猪钱罐的重量和装满钱后的重量，然后是几组数据，每组数据包括每种钱币的价值与重量要求出重量最少能装满钱罐时的最大价值 #include<iostream> #include<string> #include<algorithm> #include<cs...
HDU5534--Partial Tree (完全背包)
点击打开链接思路：总度数为2n-2，由于每个节点都至少要有1个度，所以可以看做把剩余n-2个点放入n个节点的背包问题。dp[i]表示放入i个度后的最大值#include<cstdio>#include<algorithm>#include<cstring>usin...
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背包变形。对于给出的公式，...
1354 选数字 DP背包 + 数学剪枝
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1354&judgeId=187448其实这题和在若干个数字中，选取和为val，有多少种不同的选法是一样的。只不过不能直接枚举背包容量，只能用map的iterate来枚...