01背包与完全背包讲解.ppt

ACM寒假集训--01背包与完全背包
2018/5/11
2
话题引入:
小P同学爱好探险寻宝,一天他去了伊利哇呀半岛发现了一批宝藏,但不幸的是小P很懒,出门只带了一个背包,所以注定他不能带走所有的宝藏。但是小P又很贪心想带走尽量多的宝藏。。。已知每种宝贝的重量与价值是不一样的,小P很笨,没有你聪明,但是聪明的你想到了好的解决方案了吗?
2018/5/11
3
数据分析:
假设背包的容量上限为5kg
A宝贝重2kg价值3,000,000,000$
B宝贝重3kg价值4,000,000,000$
C宝贝重4KG价值6,500,000,000$
D宝贝重5KG价值6,700,000,000$
E宝贝重6KG价值10,000,000,000$
你认为怎么装才最合理为什么啊?
解题思路?
你是怎么想的啊???
2018/5/11
5
思考贪心和01背包的区别
一般同学们会考录到用贪心的算法通过求最大的性价比来填满背包,大家考录一下这样会有什么样的不妥之处。。。。
贪心与背包的不同:
首先说一下贪心是每一步都是最优的决策,就是每次方我都会放进去解决问题的目前最好的结果。
贪心虽然会带来每一次最优但是不一定是整体最优。(比如说C的性价比最高,但是放了C就不能放别的了,总价值就不如放A和B的多了)
背包可以从宏观上整体得到一个最优的结果。
2018/5/11
6
01背包原理阐述
01背包的原理其实不是很难理解,你不要被他唬住,不要畏惧,其实他也就是那么一回事。。。。
问题的特点是:每种物品一件,可以选择放1或不放0。
用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:
f[i][v] = max{f[i-1][v-p[i]] + w[i], f[i-1][v]}
在这里解释一下公式中‘,’号前面是放的状态,后面是不放的状态;
如果在这里第i件物品放的话就表明它是由第i-1的状态传递过来的并且加上新的价值w[i],如果不放就表明这里是保持第i-1的状态没有增加新的价值。
博客链接:http://blog./s/
2018/5/11
7
题目举例:HDU2602
思考一下应该怎么解决?
2018/5/11
8
你看懂了吗。。?
2018/5/11
9
代码研讨
#include <>
#define MAXN 1002
int dp[MAXN][MAXN], w[MAXN], p[MAXN];
int _max(int a, int b){
return a > b ? a : b;
}
int main(){
int n, v, T, i, j;
scanf("%d", &T);
while(T--){
scanf("%d %d", &n, &v);
for(i=1; i<=n; i++){
scanf("%d", &w[i]);
}
for(i=1; i<=n; i++){
scanf("%d", &p[i]);
}
for(i=0; i<=n; i++) dp[i][0] = 0;
for(i=0; i<=v; i++) dp[0][i] = 0;

for(i=1; i<=n; i++){
for(j=0; j<=v; j++){
dp[i][j] = dp[i-1][j];
if(j>=p[i]) dp[i][j] = _max(dp[i-1][j], dp[i-1][j-p[i]]+w[i]);
}
}
printf("%d\n", dp[n][v]);
}
return 0;
}
一维数组的优化
#include <>
#include <>
#define MAXN 1002
int max_num(int a, int b){
return a > b? a : b;
}
int dp[MAXN], w[MAXN], p[MAXN];
int main(){
int n, v, T, i, j;
scanf("%d", &T);
while(T--){
scanf("%d %d", &n, &v);
for(i=1; i<=n; i++){
scanf("%d", &w[i]);
}
for(i=1; i<=n; i++){
scanf("%d", &p[i]);
}
2018/5/11
10
for(i=0; i<=v; i++){
dp[i] = 0;
}
for(i=1; i<=n; i++){
for(j