开心的金明动态规划

题意：0-1背包经典题；
不多述，直接上代码：
【开心的金明】1.二维数组表示法：

#include #include #include #include using namespace std; int dp[30][30005]; int main () { int R,N; int v,m; scanf("%d%d",&R,&N); for(int i=1; i<=N; i++){ scanf("%d%d",&v,&m); for(int j=1; j<=R; j++){ dp[i][j]=(i==1?0:dp[i-1][j]); if(j>=v) dp[i][j]=max(dp[i][j],dp[i-1][j-v]+v*m); } } printf("%d\n",dp[N][R]); return 0; }

2：一维数组表示法：

#include #include #include #include using namespace std; int dp[30005]; int main () { int R,N; int v,m; scanf("%d%d",&R,&N); for(int i=1; i<=N; i++){ scanf("%d%d",&v,&m); for(int j=R; j>=v; j--) dp[j]=max(dp[j],dp[j-v]+v*m); } printf("%d\n",dp[R]); return 0; }