poj 3624 0/1背包暨0/1背包的学习-白红宇

poj 3624 0/1背包暨0/1背包的学习

阅读量：6623 次

发布时间：2019-06-25

本文共 1790 字，大约阅读时间需要 5 分钟。

AC的代码：

#include 
     
      #include 
      
       using namespace std;#define MAX(a,b) (a>b?a:b)#define N 12881#define M 3403int value[N];int W[M],D[M];int main(){    int n,m,i,j;    freopen("in.txt","r",stdin);    while(scanf("%d%d",&n,&m)!=EOF)    {        for(i=1; i<=n; i++)        {            scanf("%d%d",&W[i],&D[i]);        }       // for(i=0;i
       
        =W[i]; j--)            {                value[j]=MAX(value[j-W[i]]+D[i],value[j]);            }        }        printf("%d\n",value[m]);    }    return 0;}

这是我学习0/1背包是写的这题的代码,很可惜,MLE.后来看别人的才知道把二维数组转换为以为数组才可以：

推荐这个博客给大家里面有图示，可以帮助理解。

关键是理解这个方程就好：value[i][j]=max(value[i-1][j],D[i]+value[i-1][j-w[i]]);

#include 
     
      #include 
      
       using namespace std;#define MAX(a,b) (a>b?a:b)#define N 12881#define M 3403int value[N][M];int W[N],D[N];int main(){    int n,m,i,j,max;    freopen("in.txt","r",stdin);    while(scanf("%d%d",&n,&m)!=EOF)    {        for(i=1; i<=n; i++)        {            scanf("%d%d",&W[i],&D[i]);        }        for(i=0;i
       
        =1; j--)            {                if(W[i]<=j)  //当前物品的容量小于背包容量                {                    //value[i][j]=MAX(D[i]+value[i-1][j-W[i]],value[i-1][j]);                    if(D[i]+value[i-1][j-W[i]]>value[i-1][j])                        //当前物品的价值加上背包剩下的空间能放下的总量的物品的价值                        //大于上一次选择的最佳方案则更新c[i][j]                    {                        value[i][j]=D[i]+value[i-1][j-W[i]];                    }                    else                    {                        value[i][j]=value[i-1][j];                    }                    }                else                {                    value[i][j]=value[i-1][j];                }            }        }        printf("%d\n",value[n][m]);    }    return 0;}