题号：P1049
标签：动态规划

原题传送门

思路

这道题乍看有点难度，但其实就是个容量等于价格的背包问题QAQ。

关于背包问题，详见我的另一篇博文：【洛谷】采药

此题只要把上一题的代码稍作做些修改即可~

设dp[i][j]为前i个物体装入容量为j的背包的最大价值,w[i]，v[i]分别为第i个物品的重量和价格。

状态转移方程为：

dp[i][j]=dp[i-1][j]                               (j<w[i])
dp[i][j]=max{dp[i-1][j],dp[i-1][j-w[i]]+v[i]}     (j≥w[i])

水代码开始~（逃~~~）

Code

//经典背包，无需解释 
#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

int T,M,w[31],v[31],dp[31][20001];

int main()
{
   //初始化 
   for(int i=1;i<=M;i++)
   {
       dp[i][0]=0;
   }
   for(int i=1;i<=T;i++)
   {
       dp[0][i]=0;
   }
   
   //读入 
   scanf("%d%d",&T,&M);
   for(int i=1;i<=M;i++)
   {
       scanf("%d",&w[i]);
       v[i]=w[i];
   }
   
   //装叉走起
   for(int i=1;i<=M;i++)
   {
       for(int j=1;j<=T;j++)
       {
           if(j<w[i])
           {
               dp[i][j]=dp[i-1][j];
           }
           else
           {
               dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
           }
       } 
   }
   
   //输出
   printf("%d",T-dp[M][T]);
   
   return 0;
}

此外还可以把空间压为一维。

Code2.0

//经典背包，无需解释 
#include<iostream>
#include<cstdio>
#include<cmath>
 

using namespace std;

int T,M,w[31],v[31],dp[20001];

int main()
{
   for(int i=1;i<=T;i++)
   {
       dp[i]=0;
   }
   scanf("%d%d",&T,&M);
   for(int i=1;i<=M;i++)
   {
       scanf("%d",&w[i]);
       v[i]=w[i];
   }
   for(int i=1;i<=M;i++)
   {
       for(int j=T;j>=1;j--)
       {
           if(j>=w[i])
               dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
       } 
   }
   printf("%d",T-dp[T]);
   return 0;
}

版权声明：本文为gongdakai原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/gongdakai/p/11031476.html