学习的视频

动态转移方程:
dp[i][j]=max(dp[i-1][j] , dp[i-1][ j-p[i] ]+m[i]);

#include <iostream>
#include<cstring>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;

int main()
{
    int n,x;
    while(~scanf("%d %d",&n,&x))
    {
        int p[n+1],m[n+1];
        int i,j;
        int dp[n+1][x+1]={{0}};

        for(i=1;i<=n;i++)
        {
            cin>>p[i]>>m[i];

        }
         for(i=0;i<=x;i++)
        {
            dp[0][i]=0;
        }

        for(i=1;i<=n;i++)
        {
            for(j=1;j<=x;j++)//j表示当前背包容量
            {
                if(p[i]> j)//如果该物品容量大于当前背包容量
                {
                    dp[i][j]=dp[i-1][j];
                }
                else
                {
    dp[i][j]=max(dp[i-1][j] , dp[i-1][ j-p[i] ]+m[i]);
                }

            }
        }
        cout<<dp[n][x]<<endl;
    }
    return 0;
}

因为每层都只于上层有关,故压缩数组,
又因为从小到大会覆盖到上层数据,故从小到大更新数据
优化后:

#include <iostream>
#include<cstring>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;

int main()
{
    int n,x;
    while(~scanf("%d %d",&n,&x))
    {
        int p[n+1],m[n+1];
        int i,j;
        int dp[x+1]= {0};

        for(i=1; i<=n; i++)
        {
            cin>>p[i]>>m[i];

        }
        for(i=0; i<=x; i++)
        {
            dp[i]=0;
        }

        for(i=1; i<=n; i++)
        {
            for(j=x; j>=1; j--) //j表示当前背包容量
            {
                if(j>=p[i])
                {
                    dp[j]=max(dp[j], dp[j-p[i] ]+m[i]);
                }

            }
        }

        cout<<dp[x]<<endl;
    }
    return 0;
}

dp动态规划 背包问题