分类 背包问题 下的文章

BZOJ 1655: [Usaco2006 Jan] Dollar Dayz 奶牛商店

Description约翰到奶牛商场里买工具.商场里有K(1≤K≤100).种工具,价格分别为1,2,…,K美元.约翰手里有N(1≤N≤1000)美元,必须花完.那他有多少种购买的组合呢?Input仅一行,输入N,K.Output不同的购买组合数.Sample Input5 3Sample Output5Solution完全背包,需要高精度Code#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 2000- 阅读剩余部分 -

BZOJ 2427: [HAOI2010]软件安装

题目描述现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上,使得这些软件的价值尽可能大(即Vi的和最大)。但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件i依赖软件j)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够发挥的作用为0。我们现在知道了软件之间的依赖关系:软件i依赖软件Di。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则Di=0,这- 阅读剩余部分 -

计蒜客 习题:蒜头君的购物袋 1

前言我的 DP 好弱啊。题目描述给你一个袋子,容量为 V。再给你一堆物品,每个容量为 Vi 。求袋子剩余空间最小是多少。输入格式第一行输入一个整数 V ,表示购物袋的容量。第二行输入一个整数 N,表示蒜头君购买的 n 件物品。接下来输入 n 行,每行输入一个整数 表示每个物品的体积输出格式一个整数,最小空间题解这是一道裸的01背包题,把每个物品看做价值和重量都是一样的,这样就转换到了求最大价值上,直接跑一遍背包算出,由于价值和容量一样,所以最大价值就是最大占的容量,用总容量减去求得的值就是答案了。代码1 未压维#include <cstdio> #include- 阅读剩余部分 -