首页 > 代码库 > 【解题报告】[动态规划]RQNOJ PID2 / 开心的金明
【解题报告】[动态规划]RQNOJ PID2 / 开心的金明
原题地址: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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。