数塔最大路径和

数塔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//数塔
/*
 时间复杂度：O(n^2)
 */
#include<iostream>
using namespace std;
const int maxn = 1000;
int f[maxn][maxn],dp[maxn][maxn];
void Create_Tower(int n){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>f[i][j];
        }

    }
}//构建数塔
void Display_Tower(int n){
    cout<<"Tower:\n";
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cout<<f[i][j]<<" ";
        }
        cout<<endl;
    }
}//打印数塔
int MaxSumofPath_in_Tower(int n){//自底层而上，计算每个节点f[i][j]到最后一层的路径上可能的路径和,记为dp[i][j]
    for(int j=1;j<=n;j++){
        dp[n][j] = f[n][j];
    }//最后一排的记为自身
    for(int i=n-1;i>=1;i--){
        for(int j=1;j<=i;j++){
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1]) + f[i][j];//dp[i][j]为下一层与其邻接的两个结点中的最大值+f[i][j]
        }
    }
    return dp[1][1];//自下而上直到第一层，最后便能得到最大路径和了
}
int main(){
    int n;
    cin>>n;
    Create_Tower(n);
    Display_Tower(n);
    cout<<"maxsum: "<<MaxSumofPath_in_Tower(n);
}
/*
 input:
5
5
8 3
12 7 16
4 10 11 6
9 5 3 9 4
 output:
Tower:
5
8 3
12 7 16
4 10 11 6
9 5 3 9 4
maxsum: 44


 */

最大和连续子序列

对最大下标n的序列
要求最大和连续子序列，
这个子序列可能是以A[i]开始，A[n]结尾的某个序列，
也可能是整个序列中间的某个连续子序列，即之前n-1个元素的序列的解，它也必然是以某个元素结尾的序列
因此问题转化为求以各个元素为结尾的子序列的最大和，最后取其中最大的即可。
具体来说：
现在把dp数组考虑为dp[i]为以i结尾的序列的最大和,则dp[i]要么是单个元素A[i]，要么是A[i]+以A[i-1]为结尾的最大和
即，dp[i]=max{dp[i-1]+A[i],A[i]}
那么最终整个序列中的最大序列和就是dp数组中的最大值

时间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
using namespace std;
void InputA(int n,int *A){
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
}
void OutputA(int n,int *A){
    for(int i=0;i<n;i++){
        cout<<A[i]<<" ";
    }
    cout<<endl;
}
void OutputDp(int n,int *dp){
    for(int i=0;i<n;i++){
        cout<<dp[i]<<" ";
    }
    cout<<endl;
}
int MaxSUM(int n,int *A){
    int *dp = new int(n);
    for(int i=0;i<n;i++){
        dp[i]=0;
    }
    dp[0] = A[0];//以A[0]结尾的最大和即它本身
    for(int i=1;i<n;i++){
        dp[i]=max(dp[i-1]+A[i],A[i]);
    }
    int maxsum=dp[0];
    for(int i=1;i<n;i++){
        if(dp[i]>maxsum){
            maxsum=dp[i];
        }
    }
    OutputDp(n,dp);
    return maxsum;
}
int main(){
    int n;
    cin>>n;
    int *A  =new int(n);

    InputA(n,A);
    OutputA(n,A);
    cout<<MaxSUM(n,A)<<endl;


}
/*
input:
6
-2 11 -4 13 -5 -2
output:
-2 11 -4 13 -5 -2 
-2 11 7 20 15 13 
20
 */

最长不下降子序列(可以不连续)

一每个元素结尾的序列，其最长度至少为1，故初始化dp[i]皆为1，
对于一个A[i]来说，以他结尾的最长不下降子序列，可以这样找：
从他开始往前找找，找到前面子序列中(遍历0～i-1)不大于它的元素A[j]并且能有dp[j]+1>dp[i]，则不断更新dp[i]=dp[j]+1;
找不到的话自然dp[i]还是1，即最长为他自身。
时间复杂度：O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//最长不下降子序列(可以不连续)
/*
 一每个元素结尾的序列，其最长度至少为1，故初始化dp[i]皆为1，
 对于一个A[i]来说，以他结尾的最长不下降子序列，可以这样找：
 从他开始往前找找，找到前面子序列中(遍历0～i-1)不大于它的元素A[j]并且能有dp[i]>dp[j]+1，则不断更新dp[i]=dp[j]+1;
 找不到的话自然dp[i]还是1，即最长为他自身。
 时间复杂度：O(n^2)
 */
#include <iostream>
using namespace std;
const int maxn=1000;
int A[maxn],dp[maxn];
int Input_A(int n){
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
}
int Output_dp(int n){
    cout<<"dp: "<<endl;
    for(int i=0;i<n;i++){
        cout<<dp[i]<<" ";
    }
}
int LIS(int n){
    for(int i=0;i<n;i++){
        dp[i] = 1;
    }
    for(int i=1;i<n;i++){
        for(int j=i-1;j>=0;j--){
            if(A[j]<=A[i]&&(dp[j]+1>dp[i])){
                dp[i] = dp[j]+1;
            }
        }
    }//转移
    int maxlength=dp[0];
    for(int i=1;i<n;i++){
        if(dp[i]>maxlength){
            maxlength = dp[i];
        }
    }
    return maxlength;

}
int main(){
    int n;
    cin>>n;
    Input_A(n);
    cout<<"maxlength: "<<LIS(n)<<endl;
    Output_dp(n);

}
/*
Input：
7
1 2 3 -1 -2 7 9

output:
maxlength: 5
dp:
1 2 3 1 1 4 5


input:
8
1 2 3 -9 3 9 0 11

output:
maxlength: 6
dp:
1 2 3 1 4 5 2 6
 */

最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//最长公共子序列

/*
定义dp[][],dp[i][0]=dp[0][j]=0,可以表示字母与空集的最长公共子序列为0；dp[0][0]自然是空对空公共序列为空了。
 那么每个序列的正式下标自然从1开始了，dp[i][j]表示A的前i个元素与B的前j个元素的最长公共子序列大小。
 时间复杂度：O(n^2)
*/
#include<iostream>
using namespace std;
int LCS(const char *A, const char *B, int lena, int lenb){
    int length_LCS=min(lena,lenb),count=-1;
    char LCS[length_LCS+1];
    int **dp= new int*[lena+1];
    for(int i=0;i<lena+1;i++){
        dp[i] =new int[lenb+1];
    }
    for(int i=0;i<=lena;i++){
        dp[i][0] = 0;
    }
    for(int i=0;i<=lenb;i++){
        dp[0][i] = 0;
    }
    for(int i=1;i<=lena;i++){
        for(int j=1;j<=lenb;j++){
            if(A[i]==B[j]) dp[i][j] = dp[i-1][j-1]+1;
            else dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
        }
    }
    for(int i=0;i<=lena;i++){
        for(int j=0;j<=lenb;j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }//打印dp
    int i=lena,j=lenb;
    //cout<<dp[i][j]<<A[i]<<endl<<endl;
    while(dp[i][j]){
        if(dp[i][j] == dp[i-1][j]) i--;
        else if(dp[i][j] == dp[i][j-1]) j--;
        else if(dp[i][j]>dp[i-1][j-1]){
            LCS[++count] =A[i];
            //cout<<A[i]<<endl<<endl;
            i--;
            j--;
        }
    }//推出一条最长公共子序列
    cout<<"LCS: "<<endl;
    for(int k=count;k>=0;k--){
        cout<<LCS[k]<<" ";
    }//打印最长公共子序列
    cout<<endl;
    return dp[lena][lenb];//返回最长公共子序列长度                 
}
int main() {
    int lena,lenb;
    cin>>lena;
    char A[lena+1];
    for(int i=1;i<=lena;i++){
        cin>>A[i];
    }
    cin>>lenb;
    char B[lenb+1];
    for(int i=1;i<=lenb;i++){
        cin>>B[i];
    }
    int length_of_LCS=LCS(A,B,lena,lenb);
    cout<<"length of LCS: "<<length_of_LCS;

}

/*
input:
 8
sadstory
10
adminsorry

output:
0 0 0 0 0 0 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1
0 1 2 2 2 2 2 2 2 2 2
0 1 2 2 2 2 3 3 3 3 3
0 1 2 2 2 2 3 3 3 3 3
0 1 2 2 2 2 3 4 4 4 4
0 1 2 2 2 2 3 4 5 5 5
0 1 2 2 2 2 3 4 5 5 6
LCS:
a d s o r y
6
 */

最小编辑距离

编辑距离问题就是问把一个单词变成另一个单词最少需要多少步操作（插入，删除，替换）
时间复杂度：O(n^2)

（*）这段主要是讨论根据哪一个编辑距离来计算A到A[i]为止和和B中到B[j]为止的两段序列的编辑距离dp[i] [j]我们希望编辑距离自然是越小越好

拿dp[i-1] [j]来说，若用它来算dp[i] [j],由于dp[i-1] [j]确定了，则现在由于新加入了一个A[i]，故必然要多一次操作，即dp[i] [j]=dp[i-1] [j]+1;
选到dp[i] [j-1]算dp[i] [j]也是同理，故我们选他俩中小的操作，即希望最后得到的编辑距离能尽可能小

而若我们是拿dp[i-1] [j-1]来算dp[i] [j]，即A和B都新放了一个元素，即A[i]和B[j]，那就需要讨论了
1.若A[i]=B[j]，则新加入的这俩元素不需要修改，对编辑距离没有影响，故dp[i] [j] = dp[i-1] [j-1]
2.而若A[i]！=B[j]，则在dp[i] [j]的基础上，把A[i]改成B[i]或是把B[i]改成A[i]即可， 故dp[i] [j] = dp[i-1] [j-1]+1;
我们把两种情况综合一下，即基于dp[i-1] [j-1]，A[i]和B[j]等,则不动；不等则动一下（即加1），

​ 因此我们添加一个变量I，I = (A[i]!=B[j])?1:0; 得dp[i] [j] = dp[i-1] [j-1]+I

故综上所述，就有了dp[i] [j]=min{dp[i-1] [j]+1 , dp[i] [j-1]+1 , dp[i-1] [j-1]+I}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
//编辑距离问题
/*
 编辑距离问题就是问把一个单词变成另一个单词最少需要多少步操作（插入，删除，替换）
 时间复杂度：O(n^2)
 */
#include<iostream>
using namespace std;
void Init_dp(int **dp,int lena,int lenb){//dp的形状为（lena+1）x(lenb+1)
    for(int i=0;i<=lena;i++){
        dp[i][0] = i;
    }//与下面相反，即做i次删除操作
    for(int i=0;i<=lenb;i++){
        dp[0][i] = i;
    }//长度为0的单词变为长度为i的单词操作自然是插入i此
}
void Print_dp(int **dp,int lena,int lenb){
    for(int i=0;i<=lena;i++){
        for(int j=0;j<=lenb;j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }//打印dp矩阵
}


int EditDistance(const char *A, const char *B, int lena, int lenb){
    int **dp= new int*[lena+1];
    for(int i=0;i<lena+1;i++){
        dp[i] =new int[lenb+1];
    }//构建dp数组
    Init_dp(dp,lena,lenb);//初始化dp数组
    int I=0;
    for(int i=1;i<=lena;i++){
        for(int j=1;j<=lenb;j++){
            I = (A[i]!=B[j])?1:0;//即A[i]!=B[i],则I=1，多一位需要修改的元素；
                                 //A[i]=B[i],则I=0，则这位元素我需修改
            dp[i][j]=min( min(dp[i-1][j]+1,dp[i][j-1]+1)  ,  dp[i-1][j-1]+I);
        }//看上面（*）处的解释
    }
    Print_dp(dp,lena,lenb);
    return dp[lena][lenb];
}

int main(){
    int lena,lenb;
    cin>>lena;
    char A[lena+1];
    //gets(A+1);
    for(int i=1;i<=lena;i++){
        cin>>A[i];
    }
    cin>>lenb;
    char B[lenb+1];
    for(int i=1;i<=lenb;i++){
        cin>>B[i];
    }
    cout<<EditDistance(A,B,lena,lenb);

}
/*
input:
10
ALTRUISTIC
9
ALGORITHM
output
0 1 2 3 4 5 6 7 8 9
1 0 1 2 3 4 5 6 7 8
2 1 0 1 2 3 4 5 6 7
3 2 1 1 2 3 4 4 5 6
4 3 2 2 2 2 3 4 5 6
5 4 3 3 3 3 3 4 5 6
6 5 4 4 4 4 3 4 5 6
7 6 5 5 5 5 4 4 5 6
8 7 6 6 6 6 5 4 5 6
9 8 7 7 7 7 6 5 5 6
10 9 8 8 8 8 7 6 6 6
6
 */

最少硬币兑换问题

输入：
给定n种面值的硬币，d1=1，d1<d2<d3<d4<…..<dn，
硬币数量不限
输出：
最少用多少个硬币可以兑换金额N
时间/空间复杂度：O(nN)

想法：

当我们现在有了d[1]~d[i]，需要兑换的金额为j

此时有两种可能：

  • 我们不用d[i]，只用d[1]~d[i-1]兑换出N来，

    如有1，2，5或1，2都可以把4、6给兑换出来

    那我们所需的硬币数量即dp[i-1] [j]，即dp[i] [j] = dp[i-1] [j]；

  • 用到至少一个d[i]，那么dp[i] [j] = dp[i] [j-d[i]]+1

    如我们要用1 2 5兑换8块，8-5=3，我们用1 2 5兑换3块时需要2个币， 现再加上一个5块的即可，即2+1=3个币。

由此我们只要看哪种方法用的硬币少就用哪种方法。

即：dp[i] [j] = min(dp[i-1] [j]，dp[i] [j-d[i]]+1);🍎

这里有个需要注意的问题时：j-d[i]可能小于0，如想用1 2 5兑换3块，3-5 = -2，本意是想用1 2 5兑换-2块的硬币数量再加上一个五块硬币🪙即可，但去兑换 -2 块这显然不对，这就说明我们兑换3块钱时压根本没法用上5块的硬币。

因此我们对上面👆🍎处min()的第二项作出修改，

  • 如果j-d[i] >= 0，则可以把两种方法比较一下，看哪个小就选哪个，即式🍎

  • 当然如果j-d[i] < 0，那就把第二项改为一个特别大的数(如：9999)，这样我们最后自然选的就是第一种方法了。

因此我们把第二项写作var ，var = ( j>=d[i] ) ? ( dp[i] [j-d[i]] + 1 ) : 9999

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//硬币兑换问题
//
#include <iostream>
using namespace std;
void Init_dp(int **dp,int n,int N){
    for(int i=0;i<=n;i++){
        dp[i][0] = 0;
    }
    for(int j=0;j<=N;j++){
        dp[0][j] = 0;
        dp[1][j] = j;//规定d1=1，则用j个一块钱可以兑换j块钱
    }
}
void Print_dp(int **dp,int n,int N){
    for(int i=0;i<=n;i++){
        for(int j=0;j<=N;j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }//打印dp
}
int CoinChanging(const int *d,int n,int N){
    int **dp= new int*[n+1];
    for(int i=0;i<n+1;i++){
        dp[i] =new int[N+1];
    }
    Init_dp(dp,n,N);
    for(int i=2;i<=n;i++){
        for(int j=1;j<=N;j++){
            int var= (j>=d[i])?(dp[i][j-d[i]]+1):9999;
            //cout<<var<<" ";
            dp[i][j] = min(dp[i-1][j],var);
        }
        //cout<<endl;
    }
    Print_dp(dp,n,N);
    cout<<"兑换"<<N<<"块钱需要："<<dp[n][N]<<"个币";
    return dp[n][N];
}
int main(){
    int n;
    cin>>n;
    int *d = new int[n+1];
    for(int i=1;i<=n;i++){
        cin>>d[i];
    }
    int N;cin>>N;
    CoinChanging(d,n,N);
    //cout<<"兑换"<<N<<"块钱需要："<<CoinChanging(d,n,N)<<"个币";
}
/*
input
3
1 2 5
8
output
0 0 0 0 0 0 0 0 0 
0 1 2 3 4 5 6 7 8 
0 1 1 2 2 3 3 4 4 
0 1 1 2 2 1 2 2 3 
兑换8块钱需要：3个币
*/

最长回文子串

/*
给出一个字符串S，求S的最长回文子串的长度
如：
input:
KATCJUJCTAUHBNC
output：
ATCJUJCTA,长度为9
*/

🍎思路：

我们以s表示字符串

我们以dp[i] [j]表示s[i]到s[j]这段子串是否为回文，是则为1，不是则为0

  1. 想到边界（初始条件）：
    dp[i] [i] = 1;//长度为1的回文

    dp[i] [i+1]=(s[i]==s[i+1])?1:0 ;//长度为2的回文

  2. 我们希望转移方程简单化：

    对于s[i]到s[j]是否为回文的判断，我们希望做到

    若s[i]！=s[j]，那s[i]到s[j]自然不是回文

    若s[i]= =s[j]，则看s[i+1]与s[j-1]，我们希望若s[i+1]==s[j-1]则可以判断s[i]到s[j]是回文

    那么我们就希望在判断长为L时，长度<L的串的回文判断已经有了,

    正是出于这个目的，我们才写了上面的dp[][]初始化，即先得到了对长度为1和长度为2的子串是否为回文的判断。

    基于对长度为1和2的子串的判断，去算出对长度为3的，长度为4.。。。。的判断，这样最后就得到了所有长度的回文的判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//最长回文字串
/*
给出一个字符串S，求S的最长回文子串的长度
如：
字符串
KATCJUJCTAUHBNC
希望得到：
ATCJUJCTA,长度为9
*/
#include<iostream>
using namespace std;
void InitDp(int n,int **dp,char *s,int &maxlength){//边界（基本情况）
    for(int i=0;i<n;i++){
        dp[i][i] = 1;//长度为1的回文
        if(i<n-1){
            dp[i][i+1]=(s[i]==s[i+1])?1:0 ;//长度为2的回文
            maxlength=2;
        }
    }
}
void GetS(int n,char *s){
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
}

int HW(int n,int **dp,char *s,int &maxlength){//可看上面🍎处的解释
    

    for(int L=3;L<=n;L++){//转移方程
        for(int i=0;i+L-1<n;i++){
            int j = i+L-1;
            if(s[i] == s[j] && dp[i+1][j-1]==1){
                dp[i][j] =1;
                maxlength = L;
                //cout<<L;
            }
        }
    }
    
    return maxlength;
}
void OutputResult(int n,int **dp,char *s,int &maxlength){
    cout<<"最长回文子串长度为："<<maxlength<<endl;
    cout<<"此时最长回文子串为：\n";
    int count=0;
    for(int i=0;i+maxlength-1<n;i++){
        
        int j=i+maxlength-1;
        if(dp[i][j]==1){
            count++;
            cout<<count<<"."<<" ";
            for(int k=i;k<=j;k++){
                cout<<s[k]<<" ";
            }
            cout<<"\n";
        }
    }
    cout<<endl;
}
int main(){
    int n;
    cin>>n;
    char s[n];
    GetS(n,s);
    int maxlength=1;
    int **dp = new int *[n];
    for(int i=0;i<n;i++){
        dp[i]=new int(n);
    }
    
    InitDp(n,dp,s,maxlength);//初始化dp数组
    HW(n,dp,s,maxlength);
    
    OutputResult(n,dp,s,maxlength);
}

/*
input1:
10
asaghgjkjo

output1:
最长回文子串长度为：3
此时最长回文子串为：
1. a s a 
2. g h g 
3. j k j

又如：
input2:
15
KATCJUJCTAUHBNC
output2
最长回文子串长度为：9
此时最长回文子串为：
1. A T C J U J C T A 
*/

01背包

/*

给定n种物品，每种物品一个

每个物品有其重量，有其价值

现在给你一个容量为V的包，

问怎么往里放物品，能让包里物品的总价值最大。

*/

直接去想怎么样价值最大有点突兀，因为各个物品的重量和价值不同，

一个容量为10kg的包，可能放进去3个物品占到9kg，也可能放进去5个物品占到8kg

我们的想法是用dp[i] [v]表示用前i个物品能放入容量v千克的包的时候时候，这i个物品的总价值

自然物品i至少能放入容量为w[i]的包，故v的范围为w[i]~V，而i的范围为1～n(dp二维数组中还会有第0行，看下面说的边界)

另有边界：

dp[0] [v]=0，无论拿来多大的包不放东西进去能获得的价值当然为0;

dp[i] [0]=0,包容量为零自然价值为0

由此我们得到了用前i个物品放入容量为w[i]的包的总价值，放入容量为w[i]+1的包的总价值。。。。放入容量为V的包的的总价值

由此我们得到前1个物品可能装成的重量的总价值，前两个，前三个。。。。。前n个物品可能装成重量的总价值

此时我们只要选择其中最大的即可，即最后返回的应该是最大的一个dp[i] [v]

dp[i] [v]怎么求呢？考虑v容量的包，现考虑物品i放入时的策略

如果不把物品i放入包中，则最大价值仍是前i-1件物品放进去容量v得到的最大价值,即dp[i-1] [v]；

如果把物品i放入包中，则最大价值为dp[i-1] [v-w[i]]+c[i]

我们自然选这两个决策中获得价值最大的一个，

(因为同样是容量v，而我们的物品价值并不是从小到大排列的，故我们是要考虑要不要把其他物品拿出来而选择把物品i放进去的。)

由此我们得到(dp[i] []这一行，（ 1<= i <=n）)：

​ dp[i] [v] = max{ dp[i-1] [v] , dp[i-1] [v-w[i]]+c[i] }（w[i]<= v <= V）

而当包的容量小于w[i]，物品i没法放进去，自然用物品1~i-1放进去了
dp[i] [v]=dp[i-1] [v];

由此dp[i] []这一行的转移方程即为：

dp[i] [v] = max{ dp[i-1] [v] , dp[i-1] [v-w[i]]+c[i] }（w[i]<= v <= V）

dp[i] [v]=dp[i-1] [v] （0<= v <=w[i]）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/*
时间：O(nV)
空间：O(nV)
*/
#include<iostream>
using namespace std;
void Input(int n,int *A){//初始化数组
    for(int i=1;i<=n;i++){
        cin>>A[i];
    }
    A[0]=0;//为了让w,c数组1～n与dp数组行号及物品自然序号对应自然
}
void Output(int n,int *A){//打印数组
    for(int i=0;i<=n;i++){
        cout<<A[i]<<" ";
    }
    cout<<endl;
}
void InitDp(int n,int V,int **dp){//初始化dp数组
    for(int i=0;i<n+1;i++){
        dp[i] = new int[V+1];
    }
    for(int i=0;i<=n;i++){//由于我们上面分析的边界也是dp[0][v],dp[v][0]都为0，故这里直接将整个dp数组初始化为全0
        for(int v=0;v<=V;v++){
            dp[i][v]=0;
        }
    }
}
void PrintDp(int n,int V,int **dp){//打印dp数组
    for(int i=0;i<=n;i++){
        for(int v=0;v<=V;v++){
            cout<<dp[i][v]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}
void MAXV(int n,int V,int **dp,int *w){//输出dp数组中的最大值，及我们最后的结果
    int MAXV=0;
    for(int i=1;i<=n;i++){
        for(int v=w[i];v<=V;v++){
            if(dp[i][v]>MAXV){
                MAXV=dp[i][v];
            }
        }
    }
    cout<<MAXV<<endl;
}
void Bag(int n,int V,int *w,int *c){//算法核心
    int **dp = new int*[n+1];
    InitDp(n,V,dp);
    for(int i=1;i<=n;i++){
        for(int v=0;v<w[i];v++){//包的容量小于w[i]，物品i没法放进去，自然用物品1~i-1放进去了
            dp[i][v]=dp[i-1][v];
        }
        for(int v=w[i];v<=V;v++){//容量>=w[i]，参见上面所讨论的
            dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
        }
    }
    MAXV(n,V,dp,w);
    PrintDp(n,V,dp);
}

int main(){
    int n;//n种物品
    int V;//包的容量
    cin>>n; cin>>V;
    int *w = new int[n+1];//用来存放各个物品的重量
    int *c = new int[n+1];//用来存放各个物品的价值
    Input(n,w);//输入各个物品的重量
    Input(n,c);//输入各个物品的价值
    Output(n,w);//打印w数组
    Output(n,c);//打印c数组
    Bag(n,V,w,c);//算法核心
    
}

/*
input:
5 8
3 5 1 2 2
4 5 2 1 3
0 3 5 1 2 2 
0 4 5 2 1 3 
output:
10
0 0 0 0 0 0 0 0 0 
0 0 0 4 4 4 4 4 4 
0 0 0 4 4 5 5 5 9 
0 2 2 4 6 6 7 7 9 
0 2 2 4 6 6 7 7 9 
0 2 3 5 6 7 9 9 10 

input:
5 10
2 6 3 6 9
9 1 4 9 5
0 2 6 3 6 9 
0 9 1 4 9 5 
output:
18
0 0 0 0 0 0  0  0  0  0  0 
0 0 9 9 9 9  9  9  9  9  9 
0 0 9 9 9 9  9  9  10 10 10 
0 0 9 9 9 13 13 13 13 13 13 
0 0 9 9 9 13 13 13 18 18 18 
0 0 9 9 9 13 13 13 18 18 18 
*/

因为从上面可以看出来，对i做决策的时候只与i-1有关

即，dp数组第i行只与第i-1行有关，而与本行或是甚么其他的无关了；

那我们不由的想了，

我们得到了第i-1行之后，直接在这行上面改，改完了把这行覆盖了不就得到了第i行了嘛！

哪还用得着开整整n*v这么大的数组呢。

我们仍然是对i和v循环

不同的就是我们不需要再对v<=w[i]的地方专门说明了，因为对这些元素我们取的就是和上一行一样的，原因看第一种的说明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//改进版本，优化了空间消耗
/*
时间：O(nV)
空间：O(V)
*/
        int *dp = new int[V+1];
    for(int v=0;v<=V;v++){
        dp[v] = 0;
    }
    for(int i=0;i<=n;i++){
        for(int v=V;v>=w[i];v--){
            dp[v]=max(dp[v],dp[v-w[i]]+c[i]);
        }//第一个dp[v]即上面的dp[i][v]
      //第二个dp[v]即dp[i-1][v],dp[v-w[i]]即dp[i-1][v-w[i]]
    }
    int max=0;
    for(int v=0;v<=V;v++){
        if(dp[v]>max){
            max=dp[v];
        }
    }
    cout<<max;