dp入门题解

学dp学到自闭（真的判断不出是个dp问题哇）

来看一下最近学的dp简单的题库．

１．01背包问题(P1048)

这个的特点是每种东西只能拿一次．

https://www.luogu.com.cn/problem/P1048

二维dp：

  for(int i=;i<=m;i++)

     {

         scanf("%d%d",&w[i],&val[i]);

     }

     for(int i=;i<=m;i++)

         for(int j=t;j>=;j--) //注意这个地方是倒着来的

         {

             if(j>=w[i])

             {

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

             }

             else

             {

                 dp[i][j]=dp[i-][j];

             }

         }

     printf("%d",dp[m][t]);

一维dp:

     for(int i=;i<=m;i++)

     {

         scanf("%d%d",&w[i],&val[i]);

     }

     for(int i=;i<=m;i++)

     {

         for(int j=t;j>=;j--)

         {

             if(j>=w[i])

             {

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

             }

         }

     }

01背包问题可以再加一个例题：

https://www.luogu.com.cn/problem/P1802

 for(int i=;i<=n;i++){

         for(int j=x1;j>=;j--){

             if(j>=b[i]){//如果有足够的药剂打赢别人，则看是输好还是赢好

                 f[j]=max(f[j]+a[i][],f[j-b[i]]+a[i][]);

             }

             else f[j]+=a[i][];//没有足够药剂就一个都不用直接认输，不然就浪费了药剂

         }

     }

2.完全背包(P1616)

这个与上一个的区别在于：这次的物品可以无限取．每种东西是不限量的．

代码的区别也很简单，这次是正着来的

https://www.luogu.com.cn/problem/P1616

 for(int i=;i<=n;i++)

         for(int j=w[i];j<=V;j++)

             f[j]=max(f[j],f[j-w[i]]+c[i]);

巴特西

dp入门题解

最新文章

热门文章