#include<iostream>
using namespace std;
int main()
{
int cash,n,max;
while(cin>>cash>>n)
{
max = 0;
int m[1001],v[1001];
for(int i = 0;i<n;i++) cin>>m[i]>>v[i];
bool dp[100001];
memset(dp,0,sizeof(dp));
dp[0] = true;
for(int i = 0;i<n;i++)
{
for(int j = max;j>=0;j--)
{
if(dp[j])
{
for(int k = 1;k <= m[i];k++)
{
int tmp = j+k*v[i];
if(tmp>cash) break;
dp[tmp] = true;
if(tmp>max) max = tmp;
}
}
}
}
cout<<max<<endl;
}
return 0;
}
分享到:
相关推荐
这里我把自己对poj1276的理解和分析还有源代码都放在了里面,希望对大家有所帮助。谢谢
北大POJ1276试题代码
北大POJ1276-Cash Machine 解题报告+AC代码
晒代码之二——多重背包(POJ1276)
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。