C++入门DP--动态规划_c++ dp入门

动态规划-DP

本篇为入门级，dalao绕道（捂脸）

DP最经典题目-01背包问题
思路简单清晰，将物品和价值都遍历，进行选择

    for(int i=1;i<=n;i++)//从第一个物品到最后一个物品遍历
    {
        for(int j=1;j<=m;j++)//将重量遍历
        {
            if(w[i]>j)
                dp[i][j]=dp[i-1][j];//重量超重，不放入i物品
            else
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
                //判断是否要放入i物品
        }
    }
    cout << dp[n][m] << endl ;
1
2
3
4
5
6
7
8
9
10
11
12

优化代码，时间复杂度不变，降低了空间复杂度

    for(int i=1;i<=n;i++)
        for(int j=m;j>=w[i];j--)
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    cout << dp[m] << endl ;
1
2
3
4

DP01背包升级版–完全背包
和01背包的区别在于我们同一个物品可以选择多次，次数不限。
在01中有以下code

dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
1

我们的理解是，dp[i][j]要么是不选择i，直接为dp[i-1][j]；要么是选择i，即dp[i-1][j-w[i]]+v[i],后者的理解是在i之前i的价值加上总重减去i的重量后的价值的最大值，我们现在可以多次选择i物品，所以就不用变成i之前了（i-1），就i即可

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(w[i]>j)
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
                //只有这里不同
        }
    }
    cout << dp[n][m] << endl ;
1
2
3
4
5
6
7
8
9
10
11
12

同样，我们可以减小它的空间复杂度

    for(int i=1;i<=n;i++)
        for(int j=w[i];j<=m;j++)
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    cout << dp[m] << endl ;
1
2
3
4