大家好，又见面了，我是你们的朋友全栈君。
一、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<<dp[n][m];//我们可以判断出：即使在m-1时已经装满，但是m最满足不能装更多东西的时候时，dp[n][m]是同值的
变式求值：
我们可以组合这几个关键字:恰好装满、装载量不限定、价值最大、价值最小
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
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
Input
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。
Output
Sample Input
Sample Output
#include<iostream>
#include<string.h>
#define maxn 1000+5
using 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<w[i]){
max1=w[i];//价格最大的物品放在最后选择一定是最优的
p=i;
}
}
int m;
cin>>m;
memset(dp,0,sizeof(dp));
dp[0]=1;//表示什么都不买的状态是可达的
if (m<5) cout<<m<<endl;
else{
m=m-5;
w[p]=m+1;//小技巧，使得怎么都不能选到这个物品
for(int i=1;i<=n;i++){
for(int j=m;j>=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))<<endl;
}
}
return 0;
}
2、hdu2602 Bone Collector（情况2）
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 ?
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.
31).
#include<iostream>
#include<string.h>
#define maxn 1000+5
using 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<<dp[m]<<endl;
}
return 0;
}
3、hdu2955（情况2）
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.
Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .
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.
#include<iostream>
#include<string.h>
#define maxn 10000+5
#define esp 0.0000001
using 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<<i<<endl;
}
return 0;
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/155073.html原文链接：https://javaforall.net
