背包问题（模板

_{哼哼哼啊啊啊啊啊……顾冥思彝，就是背包出问题了……（bushi}

一个人在旅途中的人有一个最多能用M公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.求此人能获得最大总价值。

Input

第1行：两个整数，M（背包容量，M<=200）和n（物品数量，n<=30）；
第2至n+1行：每行两个整数Wi,Ci，表示每个物品的重量和价值。

Output

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

样例输入

10 4
2 1
3 3
4 5
7 9

样例输出

12

code

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,m,w[901],c[901],f[1501];
 4 int main()
 5 {
 6     cin>>m>>n;
 7     for(int i = 1;i <= n;i++) cin>>w[i]>>c[i];
 8     for (int i = 1;i <= n;i++) for (int j = m;j >= w[i];j--)  f[j] = max(f[j], f[j - w[i]] + c[i]);
 9     cout<<f[m];
10     return 0; 
11 }