#include<iostream>
#include<algorithm>
using namespace std;


int arr[100005];

int bill[100];
int main(){
	int cash,n;
	int tmp1,tmp2,tmp;
	while(cin>>cash>>n){
		int num=0;
		if(n==0||cash==0) {cout<<'0'<<endl; continue;}
		memset(arr,0,sizeof(arr));
		for(int i=0;i<n;i++){
			cin>>tmp1>>tmp2;
			if(tmp1>cash/tmp2) tmp1=cash/tmp2;
			tmp=tmp1;
			int j=0,c=0;
			while(tmp1>>1){
				bill[num++]=tmp2*(1<<j);
				
				c+=(1<<j);
				j++;
				tmp1=tmp1>>1;
			}
			bill[num++]=tmp2*(tmp-c);
		}
		arr[0]=1;
		for(int k=0;k<num;k++){
			for(int ii=cash;ii>=bill[k];ii--) if(arr[ii-bill[k]]) { arr[ii]=1;}
		}
		for(int k=cash;k>=0;k--) {
			if(arr[k]) {
				cout<<k<<endl;
				break;
			}
		}
		
	}
	cin>>n;
}

• Re:大家帮忙看一下 实在挑不出错来 我是用多重背包解的报 WA (0) tintsing 2009-07-23 14:31:18
• Re:大家帮忙看一下 实在挑不出错来 我是用多重背包解的报 WA (978) y07yangruilong 2009-08-22 10:29:10
• Re:大家帮忙看一下 实在挑不出错来 我是用多重背包解的报 WA (143) JustForU 2010-09-23 19:36:56