水题的ZZH【01背包】+【一维数组模板实现】

题目描述

ZZH是北化acm界新生代的大佬&＃xff0c;每天会和无数来自全球各地的大佬进行交流。但是&＃xff0c;ZZH每天水群的时间有限。ZZH想尽可能多的和更强的大佬进行交流。他把每个大佬的实力用一个数字Ω表示出来&＃xff0c;并且每天和Ω总和最高的几位大佬进行交流。但是ZZH正在忙着水群&＃xff0c;于是把这个问题交给了你。事成之后&＃xff0c;ZZH会给你2147483647%1的金币作为奖励

输入

单组数据

第一行两个整数n&＃xff0c;m&＃xff0c;分别代表今天ZZH水群的时间&＃xff08;以分计算&＃xff09;和今天想要与ZZH交流的大佬的数量&＃xff08;<&＃61;2000&＃xff09;。

之后m行&＃xff0c;分别有两个数字&＃xff0c;代表和第i个大佬交流花费的时间&＃xff08;

输出

今天与ZZH交流的大佬的Ω的值的总和。

样例输入

70 3
71 100
69 3
1 2

样例输出

5

基础的0-1背包&＃xff0c;不会可以看看dd大牛的背包九讲---0-1背包。背包九讲转载

代码&＃xff1a;

/*0-1背包一维数组实现*/
#include
#include
int c[2008],w[2008],f[2008];
using namespace std;
int main()
{int time,n;cin>>time>>n;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)cin>>c[i]>>w[i];for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int v&＃61;time;v>&＃61;c[i];v--){f[v]&＃61;max(f[v],f[v-c[i]]&＃43;w[i]);}}cout<}