AcWing 3445. 点菜问题
原题链接
简单
作者:
Chi
,
2022-07-05 11:41:26
,
所有人可见
,
阅读 235
王道机试指南 12.7
0-1背包
(动态规划) $O(nm)$
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 1001;
int dp[MAXN];
int v[MAXN];
int w[MAXN];
int main(){
int m,n;
scanf("%d%d",&m,&n);
for(int i = 0; i < n ; i++){
scanf("%d%d",&w[i],&v[i]);
}
for(int i = 0; i <=m ; i++){
dp[i] = 0;
}
for(int i = 0;i < n ;i ++){
for(int j = m; j >= w[i] ; j-- )//倒序遍历所有j的值,保证确定dp[j]的值时,dp[j-w[j]]的值尚未被修改,完成正确的状态转移
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
printf("%d\n",dp[m]);
return 0;
}