背包*3~~~~~~~~~~~~3477：【例86.2】 01背包问题
【题目描述】
一个旅行者有一个最多能装M�公斤的背包，现在有n�件物品，它们的重量分别是W1�1，W2�2，...,Wn��.它们的价值分别为C1�1,C2�2,... ,Cn��，求旅行者能获得最大总价值。
【输入】
第一行:两个整数，M�(背包容量，M≤200�≤200)和N�(物品数量，N≤30�≤30);第22..N＋1�＋1行:每行二个整数W�，C�，表示每个物品的重量和价值。
【输出】
仅一行，一个数，表示最大总价值。
【输入样例】
10 4
2 1
3 3
4 5
7 9
【输出样例】
12
#include<bits/stdc++.h>//gezhengxu2024
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;
}