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

题目
　　现有n件物品，每一件的重量是w[i],价值是v[i]。用一个容量为c的背包来装这些东西，
问如何选择物品才能使装的物品价值最大？（每件物品只能放一次）
思路
　　我们会想该放哪i件物品到容量c的背包中呢。
　　我们可以用dp(i,j)来表示前i件物品放入容量j的背包中地最大价值。针对第i件物品,我们要先考虑
　　背包容量是否大于物品容量：
　　　　如果小于：那就不放，dp(i,j)=dp(i-1,j)。
　　　　如果大于：再考虑是否要放入：
　　　　　　　　这个时候要从放或不放第i件物品中选择一个价值更大的：dp(i,j)=max{ dp(i-1,j) , dp(i-1,j-w(i))+v(i) }
	另外，起始值dp[0][j]=dp[i][0]=0;
算法实现
　　首先用二维数组dp(i,j)变成dp[i][j]。
　　dp[i][j]有好多的状态啊，能有n*c个，这么多状态按照怎样的顺序来计算呢，所以需要找出前后关系来。
　　可以看出每一个状态都是跟上一个状态有关的，要求装i件时的价值需要知道装i-1件时候的最大价值，所以得有个外层循环i:0.....n
　　每一次都是只需要dp[i-1][1,2,3.....]中的值，所以对于j来说呢好像顺序无所谓了。
　　由此可以写出代码：
	-----------------------------------------
	#include<cstdio>
	#include <iostream>
	#include <cstring>

	using namespace std;

	int dp[1005][1005];

	int main(){
		int T;
		int M;
		int maxx=0;

		int t[1111];
		int p[1111];
		while(scanf("%d %d",&T,&M)!=EOF){
			maxx=0;
			memset(dp,0,sizeof(dp));
			memset(path,0,sizeof(path));
			for(int i=1;i<=M;i++){
				scanf("%d %d",&t[i],&p[i]);
			}
			for(int i=1;i<=M;i++){
				for(int j=1;j<=T;j++){  //因为j的顺序无所谓，for(int j=T;j>=1;j--)也可以
					if(j>=t[i]){
						dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+p[i]);       
					}else{
						dp[i][j]=dp[i-1][j];
					}
				}
			}
			printf("%d\n",dp[M][T]);
		}
		return 0;
	}
	-----------------------------------------
打印状态矩阵dp
	样例：
		10 5//容量 物品数量
		2 6//第一件物品的 重量 价值
		2 3
		6 5
		5 4
		4 6

	  | 	1    2   3    4    5    6    7    8    9    10
	--+----------------------------------------------------
	1 |	0    6    6    6    6    6    6    6    6    6
	2 |	0    6    6    9    9    9    9    9    9    9
	3 |	0    6    6    9    9    9    9    11   11   14
	4 |	0    6    6    9    9    9    10   11   13   14
	5 |	0    6    6    9    9    12   12   15   15   15

	照着这个矩阵手动推算一遍会加深理解,可以按照i：0...n,j:0...c的顺序。
	也可以按照i:0...n,j:c...0的顺序，(按照这种顺序推算，也许就可以发现后面讲的优化为一维数组的方法。)

路径记录
	之前不是说每一件物品都有放或不放两种选择吗，想要记录路径就得在放的时候给标记一下。
	关键代码如下：
	----------------------
	for(int i=1;i<=M;i++){
		//for(int j=1;j<=T;j++){
		for(int j=T;j>=1;j--){
			if(j>=t[i]){
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+p[i]);
				if(dp[i-1][j]<(dp[i-1][j-t[i]]+p[i])){//记录路径
					path[i][j]=1;//记录路径
				}//记录路径
			}else{
				dp[i][j]=dp[i-1][j];
			}
		}
	}
	----------------------
路径输出
	下面是路径矩阵
	0 1 1 1 1 1 1 1 1 1
	0 0 0 1 1 1 1 1 1 1
	0 0 0 0 0 0 0 1 1 1
	0 0 0 0 0 0 1 0 1 0
	0 0 0 0 0 1 1 1 1 1
	我们需要从这个矩阵中找出选取的哪些物品，应当从最后一个状态往前找。
	比如说有多条从一个点出发的路径，你想要找到达顶点a的路径，肯定是从a往前这一条路找过去就行了。
	代码如下：
	----------------------
	int i=M,j=T;//物品数量 背包容量
	while(i&&j){
		if(path[i][j]==1){
			printf("%d ",i);
			j-=t[i];
		}
		i--;
	}
	---------------------

一维数组优化
	还是以上面的数据为例：
	  | 	1    2   3    4    5    6    7    8    9    10
	--+----------------------------------------------------
	1 |	0    6    6    6    6    6    6    6    6    6
	2 |	0    6    6    9    9    9    9    9    9    9
	3 |	0    6    6    9    9    9    9    11   11   14
	4 |	0    6    6    9    9    9    10   11   13   14
	5 |	0    6    6    9    9    12   12   15   15   15
	观察这个矩阵，会发现某一个状态dp[i][j]跟两个元素有关，一个是它的正上方的元素，另一个是它的上一行的左边的某一个元素
	上面不是说过内层循环j可以从T....0吗，也就是j的顺序是无所谓的。
	那么我们可以用这种顺序来观察上面的矩阵，
	当我们计算dp[2][10]的时候，dp[2][10]=max{dp[1][10],dp[1][10-2]+3},结果是9，这时候可以不用把9写在第二行里，
	我们可以把它写在dp[1][10]的位置(其实这个位置原来的数据已经没用了，因为后面任何一个状态都不会再用刀这个值了)
	同样一次类推，把数据都写在第一行。
	就这样每一行从后往前计算，只用一个一维数组就够了。
	(如果每一行从前往后计算是不可以用一维数组的，比如在计算完dp[2][4]的时候，如果覆盖掉dp[1][4]的值，
	但是再计算后面的dp[2][*]的时候是会用到那个值的)
	最终代码：
------------------------------------------------
#include<cstdio>
#include <iostream>
#include <cstring>

using namespace std;

int dp[1005];
int path[1005][1005];

int main(){
    int T;
    int M;
    int t[1111];
    int p[1111];
    while(scanf("%d %d",&T,&M)!=EOF){
        memset(dp,0,sizeof(dp));
        memset(path,0,sizeof(path));
        for(int i=1;i<=M;i++){
            scanf("%d %d",&t[i],&p[i]);
        }
        for(int i=1;i<=M;i++){
            for(int j=T;j>=1;j--){
                if(j>=t[i]&&dp[j]<dp[j-t[i]]+p[i]){
                    path[i][j]=1;
                    dp[j]=dp[j-t[i]]+p[i];
                }
            }
        }
        printf("%d\n",dp[T]);

        for(int i=1;i<=M;i++){
            for(int j=1;j<=T;j++){
                printf("%d ",path[i][j]);
            }
            printf("\n");
        }

        int i=M,j=T;
        while(i&&j){
            if(path[i][j]==1){
                printf("%d ",i);
                j-=t[i];
            }
            i--;
        }
    }
    return 0;
}
/*
10 5
2 6
2 3
6 5
5 4
4 6
*/
---------------------------------------------------------