01背包

题目链接 题意：容量为V的背包，n个骨头，给出价值和体积，问最多能装多少价值的背包。 思路：01背包裸体。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年11月16日 星期三 15时14分36秒 4File Name :code/hdu/2602.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E3+7; 34int dp[N],value[N],cost[N]; 35int n,V; 36void solve(int v,int c) 37{ 38 for ( int i = V; i >= c; i --) 39 dp[i] = max(dp[i],dp[i-c]+v); 40} 41int main() 42{ 43 #ifndef ONLINE_JUDGE 44 freopen("code/in.txt","r",stdin); 45 #endif 46 int T; 47 cin>>T; 48 while (T--) 49 { 50 scanf("%d%d",&n,&V); 51 ms(dp,0); 52 for ( int i = 1 ;i <= n ; i++) scanf("%d",&value[i]); 53 for ( int i = 1; i <= n ; i++) scanf("%d",&cost[i]); 54 for ( int i = 1 ; i <= n ; i++) solve(value[i],cost[i]); 55 int ans = 0 ; 56 57 for ( int i = 0 ; i <= V ; i++) ans = max(ans,dp[i]); 58 printf("%d\n",ans); 59 } 60 61 #ifndef ONLINE_JUDGE 62 fclose(stdin); 63 #endif 64 return 0; 65}

hdu1864题目链接 题意：中文题目，不多说了。 思路：正解是01背包，呵呵呵。 出题人是傻逼吗？ 不给数据范围？ 以及，正解的01背包基于所有的发票额度的只有2位小数。这是让人猜？ 本来看到这题这么恶心时不打算写的…

题目链接 题意： 给出n个银行 ，以及抢劫每个银行可以得到的价值和被抓的概率，不同银行之间被抓的概率是相互独立的，现在给出安全概率p，只有当概率从小于安全概率时才是安全的，问最多能抢劫多少价值。

3407: [Usaco2009 Oct]Bessie’s Weight Problem 贝茜的体重问题 # Time Limit: 3 Sec Memory Limit: 128 MB Submit: 88 Solved: 79 [Submit][Status][Discuss] Description # 贝茜像她的诸多姊妹一样，因为从约翰的草地吃了太多美味的草而长出了太多的赘肉．所以约翰将她置于一个及其严格的节食计划之中．她每天不能吃多过H(5≤日≤45000)公斤的干草．贝茜只能吃一整捆干草；当她开始吃一捆干草的之后就再也停不下来了．她有一个完整

1649: [Usaco2006 Dec]Cow Roller Coaster # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 504 Solved: 265 [Submit][Status][Discuss] Description # The cows are building a roller coaster! They want your help to design as fun a roller coaster as possible, while keeping to the budget. The roller coaster will be built on a long linear stretch of land of length L (1 <= L <= 1,000). The roller coaster comprises a collection of some of the N (1 <= N <= 10,000) different interchangable components. Each component i has a fixed length Wi (1 <= Wi <= L). Due to varying terrain, each component i can be only built starting at location Xi (0 <= Xi <= L-Wi). The cows want to string together various roller coaster components starting at 0 and ending at L so that the end of each component (except the last) is the start of the next component. Each component i has a “fun rating” Fi (1 <= Fi <= 1,000,000) and a cost Ci (1 <= Ci <= 1000). The total fun of the roller coster is the sum of the fun from each component used; the total cost is likewise the sum of the costs of each component used. The cows’ total budget is B (1 <= B <= 1000). Help the cows determine the most fun roller coaster that they can build with their budget.

背包还是理解的不够透彻．． 因为每次都是用那个一维形式的． 这道题的做法类似01背包. 此外还可以有一个优化… 当n>m的时候．．．根绝抽屉原理．．一定为yes..

**Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 26534 Accepted Submission(s): 9332 ** Problem Description Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don’t know that Computer College had ever been split into Computer College and Software College in 2002. The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0<N<1000) kinds of facilities (different value, different kinds).

I NEED A OFFER! # **Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 18287 Accepted Submission(s): 7320 ** Problem Description Speakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的。Speakless没有多少钱，总共只攒了n万美元。他将在m个学校中选择若干的（当然要在他的经济承受范围内）。每个学校都有不同的申请费用a（万美元），并且Speakless估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”，他大叫一声。帮帮这个可怜的人吧，帮助他计算一下，他可以收到至少一份offer的最大概率。（如果Speakless选择了多个学校，得到任意一个学校的offer都可以）。

饭卡 # **Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 14225 Accepted Submission(s): 4945 ** Problem Description 电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。 某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。