一、01背包问题

简述：n种物品，每种一个，选或不选随你，背包一定有容量，求不超过容量的情况下，价值最大。

递归方程：dp[i][v]=max{dp[i][v],dp[i-1][v-c[i]]+w[i]}

我们要注意的是下一次背包放I个物品的状态的可达性必然要满足上一次放I-1个物品时的可达性，觉得数学归纳法可以证明出来。所以这里有个隐含的判断，就是初始时memset(dp,0,sizeof(dp));在这里已经将dp清零，所以我们可以认为在dp==0是，这一节点是没有被访问到的。因为我们取得是大的值，自然0的情况怎么都不会被选中。

递推表示：

memset(dp,0,sizeof(dp))；for(int i=1;i<=n;i++)for(int j=m;j>=c[i];j--)//注意循环下标dp[i][[j]=max(dp[i][j],dp[i-1][j-c[i]]+w[i]);//cout<

 变式求值：

我们可以组合这几个关键字:恰好装满、装载量不限定、价值最大、价值最小

1、价值最小,装载量不限定

解释：第一种可能是来酱油的，哈哈，我们什么都不装不就可以了。但是，我想在这里说明一个问题，那就是容量是一个限制条件，而不是决定最优解的条件，不要本末倒置了。

2、价值最大，装载量不限定

3、价值最大，恰好装满

解释：参考《背包九讲》

我们需要处理的是它的初始化部分

#define INF -0x3f3f3f3f........memset(dp,INF,sizeof(dp));dp[0]=0;

 为什么要这样呢？开始我是不明白的。（现在还是不怎么理解，有木有！！！！）

看看大神的抽象解释：

为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

4、价值最小，正好装满。

只需要把INF改成0x3f3f3f3f就可以了。

 

5、资源条件仅有一个。

举个例子来说。比如，给出一个数列 -1 19 0 34 -132 84 -2.........

通过选取部分数字求和，使和尽量接近一个数N，或判断是否能正好加起来是N

这道题放到平时，可能惯性思维是暴力+剪枝，可是它是一个变相的背包问题，有木有！！！~~~~~

其实就是性价比为1（价值和体积之比为1）的情况。。。。。

6、价值形式改变

相关题目

1、hdu2546 饭卡（上述第5种情况）

 

Description

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。

某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。

 

 

Input

多组数据。对于每组数据：

第一行为正整数n，表示菜的数量。n<=1000。

第二行包括n个正整数，表示每种菜的价格。价格不超过50。

第三行包括一个正整数m，表示卡上的余额。m<=1000。

n=0表示数据结束。

 

 

Output

对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。

 

 

Sample Input

1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0

 

 

Sample Output

-45 32

简要分析：在最后金额大于等于5元时，是可以买任意价格的东西的，也就是说我们可以把价格最大的东西最后买。具体的操作可以看下面的注释。

 

#include
        
         #include
         
          #define maxn 1000+5using namespace std;int dp[maxn];int w[maxn];int main(){	int n;	while(cin>>n && n){		int max1=0,p=0;		for(int i=1;i<=n;i++){			cin>>w[i];			if(max1
          
           >m;		memset(dp,0,sizeof(dp));		dp[0]=1;//表示什么都不买的状态是可达的		if (m<5) cout<
           
            <
            
             =w[i];j--){				if(dp[j-w[i]])dp[j]=1;//表示此状态可达			}	    }	    int ma=0;	    for(int i=m;i>=0;i--){		    if(dp[i]) {ma=i;break;}	    }		cout<<((m-ma)+(5-max1))<
            
           
          
         
        

2、hdu2602 Bone Collector（情况2）

Problem Description

Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …

The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?

 

Input

The first line contain a integer T , the number of cases.

Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.

 

Output

One integer per line representing the maximum of the total value (this number will be less than 2

³¹).

 

Sample Input

1 5 10 1 2 3 4 5 5 4 3 2 1

 

Sample Output

14

 

题目分析：典型的01背包问题，容量限定，求最大价值。

#include
         
          #include
          
           #define  maxn 1000+5using namespace std;long long dp[maxn];int v[maxn];int w[maxn];int main(){	int t;	cin>>t;	while(t--){		int n,m;		cin>>n;		cin>>m;		for(int i=1;i<=n;i++){			cin>>v[i];		}		for(int i=1;i<=n;i++){			cin>>w[i];		}		memset(dp,0,sizeof(dp));		for(int i=1;i<=n;i++){			for(int j=m;j>=w[i];j--){				dp[j]=max(dp[j],dp[j-w[i]]+v[i]);			}		}		cout<
           
            <
           
          
         

 

3、hdu2955（情况2）

Problem Description

The aspiring Roy the Robber has seen a lot of American movies, and knows that the bad guys usually gets caught in the end, often because they become too greedy. He has decided to work in the lucrative business of bank robbery only for a short while, before retiring to a comfortable job at a university.

For a few months now, Roy has been assessing the security of various banks and the amount of cash they hold. He wants to make a calculated risk, and grab as much money as possible.

His mother, Ola, has decided upon a tolerable probability of getting caught. She feels that he is safe enough if the banks he robs together give a probability less than this.

 

Input

The first line of input gives T, the number of cases. For each scenario, the first line of input gives a floating point number P, the probability Roy needs to be below, and an integer N, the number of banks he has plans for. Then follow N lines, where line j gives an integer Mj and a floating point number Pj .

Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .

 

Output

For each test case, output a line with the maximum number of millions he can expect to get while the probability of getting caught is less than the limit set.

Notes and Constraints

0 < T <= 100

0.0 <= P <= 1.0

0 < N <= 100

0 < Mj <= 100

0.0 <= Pj <= 1.0

A bank goes bankrupt if it is robbed, and you may assume that all probabilities are independent as the police have very low funds.

 

Sample Input

3

0.04 3

1 0.02

2 0.03

3 0.05

0.06 3

2 0.03

2 0.03

3 0.05

0.10 3

1 0.03

2 0.02

3 0.05

 

Sample Output

2 4 6

 

#include
          
           #include
           
            #define maxn 10000+5#define esp 0.0000001using namespace std;double dp[maxn];double p[100+5];int c[100+5];int main(){	int t;	cin>>t;	while(t--){		int n;		double mp;		cin>>mp>>n;		mp=1-mp;		int mc=0;		for(int i=1;i<=n;i++){			cin>>c[i]>>p[i];			mc=mc+c[i];			p[i]=1-p[i];		}				memset(dp,0,sizeof(dp));		dp[0]=1;//什么都没有偷，逃跑概率是1		for(int i=1;i<=n;i++){			for(int j=mc;j>=c[i];j--)			    if (dp[j-c[i]]>0){//表示这种状态是可达的			      	dp[j]=max(dp[j],dp[j-c[i]]*p[i]);//偷盗当前数量的钱后，最优的解肯定是逃跑概率最小的时候  			    }		}		int i;		for(i=mc;i>=0;i--){			if(dp[i]-mp>esp) break;//只要逃跑概率大于mp，那么这些状态都是可达的。		}		cout<
            <