首页 > 代码库 > 【解题报告】[动态规划]RQNOJ PID2 / 开心的金明

【解题报告】[动态规划]RQNOJ PID2 / 开心的金明

2024-07-01 22:06:28   226人阅读

原题地址：http://www.rqnoj.cn/problem/2

解题思路：背包问题。

状态转移方程：DP[i][j]=max(DP[i-v[j]][j-1]+p[j]*v[j],DP[i][j-1])

DP[i][j]表示最多话费i的钱，购买前j+1个物品所能达到的最大价值。

解题代码：

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 int DP[30005][25];
 6 int v[25];
 7 int p[25];
 8 int main()
 9 {
10     int n,m,i,j;
11     scanf("%d%d",&n,&m);
12     for(i=0;i<m;i++)
13     {
14         scanf("%d%d",&v[i],&p[i]);
15     }
16     for(i=0;i<=n;i++)
17     {
18         if(i>=v[0]) DP[i][0]=v[0]*p[0];
19         else DP[i][0]=0;
20     }
21     for(j=1;j<m;j++)
22     {
23         for(i=0;i<=n;i++)
24         {
25             if(i>=v[j]) DP[i][j]=max(DP[i-v[j]][j-1]+p[j]*v[j],DP[i][j-1]);
26             else DP[i][j]=DP[i][j-1];
27             //if(DP[i][j]>=3900) {printf("dp[%d][%d]=%d\n",i,j,DP[i][j]);getchar();}
28         }
29     }
30     printf("%d\n",DP[n][m-1]);
31     return 0;
32 }
View Code

 


联系
我们