前言 之前对0-1背包就理解的不是很好，并且时间长了会忘的。 这次又重新复习一下，理解了好几个以前没理解的点。
代码语言：javascript复制题目
现有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("%dn",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("%dn",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
*/
---------------------------------------------------------欢迎与我分享你的经验和见解。 转载请注明出处：http://taowusheng.cn/
