网站开发公司怎么选择_沈阳好的男科医院是哪一家_关键词seo是什么意思_郑州网络推广软件

题目描述

一个旅行者有一个最多能装�公斤的背包，现在有�件物品，它们的重量分别是�1，�2，...,��.它们的价值分别为�1,�2,... ,��，求旅行者能获得最大总价值。

输入

第一行:两个整数，�(背包容量，�≤200)和�(物品数量，�≤30);第2..＋�＋1行:每行二个整数�，�，表示每个物品的重量和价值。

输出

仅一行，一个数，表示最大总价值。

样例输入 复制

10 4
2 1
3 3
4 5
7 9

样例输出 复制

12

额，出乱码了，问题不大，直接上代码： 

#include<bits/stdc++.h>
using namespace std;
int w[10005],c[10005],f[1100][1100];
int main()
{int m,n;cin>>m>>n;for(int i=1;i<=n;i++)cin>>w[i]>>c[i];for(int i=1;i<=n;i++){for(int j=m;j>0;j--)if(w[i]<=j) f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);else f[i][j]=f[i-1][j];}cout<<f[n][m]<<endl;return 0;
}