我有一种简单易懂，又臭又长的做法；把每种情况都算一下。

以P1060为例

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,ans=-1;
struct node{
	int w,v,h;
};
node a[30];
bool cmp(node x,node y){
	return x.v>y.v;
}
bool cnmd(node x,node y){
	return x.v<y.v;
}
bool cnnnd(node x,node y){
	return x.w<y.w;
}
bool ctmd(node x,node y){
	return x.w>y.w;
}
bool nmd(node x,node y){
	return x.h>y.h;
}
bool wdnmd(node x,node y){
	return x.h>y.h;
}
int main(){
	int k,js;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a[i].w,&a[i].v);
		a[i].h=a[i].w*a[i].v;
	}
	
	sort(a+1,a+m+1,cmp);
	k=n,js=0;
	for(int i=1;i<=m;i++){
		if(k>=0){
			if(k-a[i].w>=0){
				js+=a[i].w*a[i].v;
				k-=a[i].w;
			}
		}else break;	
	}
	if(js>ans)ans=js;
	
	sort(a+1,a+m+1,cnmd);
	k=n,js=0;
	for(int i=1;i<=m;i++){
		if(k>=0){
			if(k-a[i].w>=0){
				js+=a[i].w*a[i].v;
				k-=a[i].w;
			}
		}else break;	
	}
	if(js>ans)ans=js;
	
	sort(a+1,a+m+1,cnnnd);
	k=n,js=0;
	for(int i=1;i<=m;i++){
		if(k>=0){
			if(k-a[i].w>=0){
				js+=a[i].w*a[i].v;
				k-=a[i].w;
			}
		}else break;	
	}
	if(js>ans)ans=js;
	
	sort(a+1,a+m+1,ctmd);
	k=n,js=0;
	for(int i=1;i<=m;i++){
		if(k>=0){
			if(k-a[i].w>=0){
				js+=a[i].w*a[i].v;
				k-=a[i].w;
			}
		}else break;	
	}
	if(js>ans)ans=js;
	
	sort(a+1,a+m+1,nmd);
	k=n,js=0;
	for(int i=1;i<=m;i++){
		if(k>=0){
			if(k-a[i].w>=0){
				js+=a[i].w*a[i].v;
				k-=a[i].w;
			}
		}else break;	
	}
	if(js>ans)ans=js;
	
	sort(a+1,a+m+1,wdnmd);
	k=n,js=0;
	for(int i=1;i<=m;i++){
		if(k>=0){
			if(k-a[i].w>=0){
				js+=a[i].w*a[i].v;
				k-=a[i].w;
			}
		}else break;	
	}
	if(js>ans)ans=js;
	printf("%d",ans);
	return 0;
}