http://acm.hust.edu.cn/vjudge/contest/125771#problem/A 水题01背包
描述
≤12880)。
考虑到重量限制约束和魅力的列表和他们的重量和愿望评级,推导出最大可能的和评级。
输入
我
输出
* 1号线:一个整数,魅力最大的和愿望可以实现,考虑到重量限制
样例输入
4 - 6
1 - 4
2 - 6
3 12
2 7
样例输出
23
___________相当水题吧 就一个简单的背包 直接模板
#include<algorithm> #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<math.h> using namespace std; #define INF 0x3f3f3f3f #define N 13000 int dp[N],a[N],q[N]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<n;i++) scanf("%d%d",&a[i],&q[i]); memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) { for(int j=m;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+q[i]); } printf("%d ",dp[m]); } return 0; }