算法提高 01背包

算是再温习一遍二维数组的写法，也有一维的，还是要多注重细节  为啥可以优化就不讲了，手动推一下就能出来

二维:

#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<cmath>using namespace std;const int MAXN=205;const int MAXM=5005;int v[MAXN];int w[MAXN];int dp[MAXN][MAXM];int main(){    int n,m;    scanf("%d %d",&n,&m);    for(int i=1;i<=n;i++)    {        scanf("%d %d",&w[i],&v[i]);    }    for(int i=1;i<=n;i++)    {        for(int j=0;j<=m;j++)        {            if(j>=w[i])                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);            else                dp[i][j]=dp[i-1][j];        }    }    PRintf("%d/n",dp[n][m]);    return 0;}一维：
#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<cmath>using namespace std;const int MAXN=205;const int MAXM=5005;int v[MAXN];int w[MAXN];int dp[MAXM];int main(){    int n,m;    scanf("%d %d",&n,&m);    for(int i=1;i<=n;i++)    {        scanf("%d %d",&w[i],&v[i]);    }    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]);        }    }    printf("%d/n",dp[m]);    return 0;}