动态规划–重拾我的“背包” – Sea_Sky

前言:

  背包问题所涉及的是经典的动态规划算法。因为长时间不AC了,渐渐感觉思维也都麻了!本文将基础的背包问题做个小结,方便以后翻阅。感兴趣的朋友也可以阅读一下~
————————
(1)如何从n个重量和价值分别为Vi、Wi的物品中选择一或多个放入最大容纳量为S的背包使其总价值最大?

输入:

5 10   (分别表示:n,S)
2 3
7 5
3 1
5 10
2 2

5 6
2 3
7 5
3 1
5 10
2 2

输出:

15

10

分析:
f[i][j]:表示背包在存放了前i件物品占据j重量时的价值
其中,1<=i<=n,0<=j<=S;

当我到达某一个状态,需要选择是否将第i件物品放入我的背包时,必须考虑值不值的问题,即:
f[i][j] = max(f[i-1][j],f[i-1]][j-w[i]]+v[i]);

理解了上面的状态转移方程之后,就可以方便得出下面的伪代码了:

  f[0…n][0…S] <- 0//初始化
  for i<-1:n
    for j<-w[i]:S
      f[i][j] = max(f[i-1][j],f[i-1]][j-w[i]]+v[i]); //状态转移

代码:

1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 const int maxn=1e3+10;
6 int f[maxn][maxn];
7 int main(){
8 //数据从文件读入
9 freopen(datain.txt,r,stdin);
10 int n,S,a,b;
11 while(scanf(%d%d,&n,&S)==2){
12 memset(f,0,sizeof(f));
13 for(int i=1;i<=n;i++){
14 scanf(%d%d,&a,&b);
15 for(int v=1;v<=S;v++){
16 if(v>=a) //do not neglect ‘v<a’
17 f[i][v] = max(f[i-1][v],f[i-1][v-a]+b);
18 else
19 f[i][v] = f[i-1][v];
20 }
21 }
22 printf(%dn,f[n][S]);
23 }
24 return 0;
25 }

以上算法的时间复杂度、空间复杂度均为:O(n*S)

f[i][j]的变化过程:

—————————–

|   0 3 3 3 3 3 3 3 3 3           |

|   0 3 3 3 3 3 5 5 8 8           |
|   0 3 3 3 4 4 5 5 8 8           |  
|   0 3 3 3 10 10 13 13 13 14 |
|   0 3 3 5 10 10 13 13 15 15 |

—————————–

 

在深入理解了状态转移方程之后,我们其实还可以对空间进行优化,仅用f[i]表示:背包质量达到i是获得的价值。对应的伪代码如下:

  f[0…S]<-0
  for i<-1:n
    for j<-S:w[i]//从右往左更新!
      f[j] = max(f[j],f[j-w[i]]+v[i]);

对空间进行优化后的代码:

1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 const int maxn=1e3+10;
6 int f[maxn];
7 int main(){
8 freopen(datain.txt,r,stdin);
9 int n,S,a,b;
10 while(scanf(%d%d,&n,&S)==2){
11 memset(f,0,sizeof(f));
12 for(int i=0;i<n;i++){
13 scanf(%d%d,&a,&b);
14 for(int v=S;v>=a;v–){
15 f[v] = max(f[v],f[v-a]+b);
16 }
17 }
18 printf(%dn,f[S]);
19 }
20 return 0;
21 }

 

(2)如何从n个重量和价值分别为Vi、Wi的物品中选择一或多个放入最大容纳量为S的背包在背包刚好装满情况下,使其总价值最大?

1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 const int maxn=1e3+10;
6 int f[maxn];
7 int main(){
8 freopen(datain.txt,r,stdin);
9 int n,S,a,b;
10 while(scanf(%d%d,&n,&S)==2){
11 for(int i=1;i<=S;i++) f[i]=-0xfffffff; //最小的int
12 f[0]=0;
13 for(int i=0;i<n;i++){
14 scanf(%d%d,&a,&b);
15 for(int v=S;v>=a;v–){
16 f[v] = max(f[v],f[v-a]+b);
17 }
18 }
19 printf(%dn,f[S]);
20 }
21 return 0;
22 }

输入:

5 10   (分别表示:n,S)
2 3
7 5
3 1
5 10
2 2

输出:14

(3)如何从n种(每种无限个)重量和价值分别为Vi、Wi的物品中选择一或多个放入最大容纳量为S的背包使其总价值最大?

1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 const int maxn=1e3+10;
6 int f[maxn];
7 int main(){
8 freopen(datain.txt,r,stdin);
9 int n,S,a,b;
10 while(scanf(%d%d,&n,&S)==2){
11 memset(f,0,sizeof(f));
12 for(int i=0;i<n;i++){
13 scanf(%d%d,&a,&b);
14 for(int v=a;v<=S;v++){
15 f[v] = max(f[v],f[v-a]+b);
16 }
17 }
18 printf(%dn,f[S]);
19 }
20 return 0;
21 }

输入:

5 6
2 3
7 5
3 1
5 10
2 2

输出:10

(4)如何从n种(每种无限个)重量和价值分别为Vi、Wi的物品中选择一或多个放入最大容纳量为S的背包在背包刚好装满情况下,使其总价值最大?

1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 const int maxn=1e3+10;
6 int f[maxn];
7 int main(){
8 freopen(datain.txt,r,stdin);
9 int n,S,a,b;
10 while(scanf(%d%d,&n,&S)==2){
11 for(int i=0;i<=S;i++) f[i]=-0xfffffff;
12 f[0]=0;
13 for(int i=0;i<n;i++){
14 scanf(%d%d,&a,&b);
15 for(int v=a;v<=S;v++){
16 f[v] = max(f[v],f[v-a]+b);
17 }
18 }
19 printf(%dn,f[S]);
20 }
21 return 0;
22 }

输入:

5 6
2 3
7 5
3 1
5 10
2 2

输出:9

———————————————-
结语:
本文限于篇幅就只是对最最基本的01背包问题作了个人的分析,后面的3个扩展只贴代码,希望感兴趣的朋友们可以旁击侧敲吧~有问题或独特见解的博友请留言~

本文链接:动态规划–重拾我的“背包”,转载请注明。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量