动态规划_01背包_一维数组_记录路径

  1 题目
  2 　　现有n件物品，每一件的重量是w[i],价值是v[i]。用一个容量为c的背包来装这些东西，
  3 问如何选择物品才能使装的物品价值最大？（每件物品只能放一次）
  4 思路
  5 　　我们会想该放哪i件物品到容量c的背包中呢。
  6 　　我们可以用dp(i,j)来表示前i件物品放入容量j的背包中地最大价值。针对第i件物品,我们要先考虑
  7 　　背包容量是否大于物品容量：
  8 　　　　如果小于：那就不放，dp(i,j)=dp(i-1,j)。
  9 　　　　如果大于：再考虑是否要放入：
 10 　　　　　　　　这个时候要从放或不放第i件物品中选择一个价值更大的：dp(i,j)=max{ dp(i-1,j) , dp(i-1,j-w(i))+v(i) }
 11     另外，起始值dp[0][j]=dp[i][0]=0;
 12 算法实现
 13 　　首先用二维数组dp(i,j)变成dp[i][j]。
 14 　　dp[i][j]有好多的状态啊，能有n*c个，这么多状态按照怎样的顺序来计算呢，所以需要找出前后关系来。
 15 　　可以看出每一个状态都是跟上一个状态有关的，要求装i件时的价值需要知道装i-1件时候的最大价值，所以得有个外层循环i:0.....n
 16 　　每一次都是只需要dp[i-1][1,2,3.....]中的值，所以对于j来说呢好像顺序无所谓了。
 17 　　由此可以写出代码：
 18     -----------------------------------------
 19     #include<cstdio>
 20     #include <iostream>
 21     #include <cstring>
 22 
 23     using namespace std;
 24 
 25     int dp[1005][1005];
 26 
 27     int main(){
 28         int T;
 29         int M;
 30         int maxx=0;
 31 
 32         int t[1111];
 33         int p[1111];
 34         while(scanf("%d %d",&T,&M)!=EOF){
 35             maxx=0;
 36             memset(dp,0,sizeof(dp));
 37             memset(path,0,sizeof(path));
 38             for(int i=1;i<=M;i++){
 39                 scanf("%d %d",&t[i],&p[i]);
 40             }
 41             for(int i=1;i<=M;i++){
 42                 for(int j=1;j<=T;j++){  //因为j的顺序无所谓，for(int j=T;j>=1;j--)也可以
 43                     if(j>=t[i]){
 44                         dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+p[i]);       
 45                     }else{
 46                         dp[i][j]=dp[i-1][j];
 47                     }
 48                 }
 49             }
 50             printf("%d\n",dp[M][T]);
 51         }
 52         return 0;
 53     }
 54     -----------------------------------------
 55 打印状态矩阵dp
 56     样例：
 57         10 5//容量 物品数量
 58         2 6//第一件物品的 重量 价值
 59         2 3
 60         6 5
 61         5 4
 62         4 6
 63 
 64       |     1    2   3    4    5    6    7    8    9    10
 65     --+----------------------------------------------------
 66     1 |    0    6    6    6    6    6    6    6    6    6
 67     2 |    0    6    6    9    9    9    9    9    9    9
 68     3 |    0    6    6    9    9    9    9    11   11   14
 69     4 |    0    6    6    9    9    9    10   11   13   14
 70     5 |    0    6    6    9    9    12   12   15   15   15
 71 
 72     照着这个矩阵手动推算一遍会加深理解,可以按照i：0...n,j:0...c的顺序。
 73     也可以按照i:0...n,j:c...0的顺序，(按照这种顺序推算，也许就可以发现后面讲的优化为一维数组的方法。)
 74 
 75 路径记录
 76     之前不是说每一件物品都有放或不放两种选择吗，想要记录路径就得在放的时候给标记一下。
 77     关键代码如下：
 78     ----------------------
 79     for(int i=1;i<=M;i++){
 80         //for(int j=1;j<=T;j++){
 81         for(int j=T;j>=1;j--){
 82             if(j>=t[i]){
 83                 dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+p[i]);
 84                 if(dp[i-1][j]<(dp[i-1][j-t[i]]+p[i])){//记录路径
 85                     path[i][j]=1;//记录路径
 86                 }//记录路径
 87             }else{
 88                 dp[i][j]=dp[i-1][j];
 89             }
 90         }
 91     }
 92     ----------------------
 93 路径输出
 94     下面是路径矩阵
 95     0 1 1 1 1 1 1 1 1 1
 96     0 0 0 1 1 1 1 1 1 1
 97     0 0 0 0 0 0 0 1 1 1
 98     0 0 0 0 0 0 1 0 1 0
 99     0 0 0 0 0 1 1 1 1 1
100     我们需要从这个矩阵中找出选取的哪些物品，应当从最后一个状态往前找。
101     比如说有多条从一个点出发的路径，你想要找到达顶点a的路径，肯定是从a往前这一条路找过去就行了。
102     代码如下：
103     ----------------------
104     int i=M,j=T;//物品数量 背包容量
105     while(i&&j){
106         if(path[i][j]==1){
107             printf("%d ",i);
108             j-=t[i];
109         }
110         i--;
111     }
112     ---------------------
113 
114 一维数组优化
115     还是以上面的数据为例：
116       |     1    2   3    4    5    6    7    8    9    10
117     --+----------------------------------------------------
118     1 |    0    6    6    6    6    6    6    6    6    6
119     2 |    0    6    6    9    9    9    9    9    9    9
120     3 |    0    6    6    9    9    9    9    11   11   14
121     4 |    0    6    6    9    9    9    10   11   13   14
122     5 |    0    6    6    9    9    12   12   15   15   15
123     观察这个矩阵，会发现某一个状态dp[i][j]跟两个元素有关，一个是它的正上方的元素，另一个是它的上一行的左边的某一个元素
124     上面不是说过内层循环j可以从T....0吗，也就是j的顺序是无所谓的。
125     那么我们可以用这种顺序来观察上面的矩阵，
126     当我们计算dp[2][10]的时候，dp[2][10]=max{dp[1][10],dp[1][10-2]+3},结果是9，这时候可以不用把9写在第二行里，
127     我们可以把它写在dp[1][10]的位置(其实这个位置原来的数据已经没用了，因为后面任何一个状态都不会再用刀这个值了)
128     同样一次类推，把数据都写在第一行。
129     就这样每一行从后往前计算，只用一个一维数组就够了。
130     (如果每一行从前往后计算是不可以用一维数组的，比如在计算完dp[2][4]的时候，如果覆盖掉dp[1][4]的值，
131     但是再计算后面的dp[2][*]的时候是会用到那个值的)
132     最终代码：
133 ------------------------------------------------
134 #include<cstdio>
135 #include <iostream>
136 #include <cstring>
137 
138 using namespace std;
139 
140 int dp[1005];
141 int path[1005][1005];
142 
143 int main(){
144     int T;
145     int M;
146     int t[1111];
147     int p[1111];
148     while(scanf("%d %d",&T,&M)!=EOF){
149         memset(dp,0,sizeof(dp));
150         memset(path,0,sizeof(path));
151         for(int i=1;i<=M;i++){
152             scanf("%d %d",&t[i],&p[i]);
153         }
154         for(int i=1;i<=M;i++){
155             for(int j=T;j>=1;j--){
156                 if(j>=t[i]&&dp[j]<dp[j-t[i]]+p[i]){
157                     path[i][j]=1;
158                     dp[j]=dp[j-t[i]]+p[i];
159                 }
160             }
161         }
162         printf("%d\n",dp[T]);
163 
164         for(int i=1;i<=M;i++){
165             for(int j=1;j<=T;j++){
166                 printf("%d ",path[i][j]);
167             }
168             printf("\n");
169         }
170 
171         int i=M,j=T;
172         while(i&&j){
173             if(path[i][j]==1){
174                 printf("%d ",i);
175                 j-=t[i];
176             }
177             i--;
178         }
179     }
180     return 0;
181 }
182 /*
183 10 5
184 2 6
185 2 3
186 6 5
187 5 4
188 4 6
189 */
190 ---------------------------------------------------------