View Code of Problem 397

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<map>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 2000000;
int dp[maxn];
int volume[maxn], value[maxn], c[maxn];
int n, v; // 总物品数，背包容量量
//val 最大容量,val 总价值,amount 数量
// 01 背包
void ZeroOnepark(int val, int vol) {
	for (int j = v ; j >= vol; j--)
		dp[j] = max(dp[j], dp[j - vol] + val);
}
//完全背包
void Completepark(int val, int vol) {
	for (int j = vol; j <= v; j++)
		dp[j] = max(dp[j], dp[j - vol] + val);
}

// 多重背包
void Multiplepark(int val, int vol, int amount) {
	if (vol * amount >= v)
		Completepark(val, vol);
	else {
 		int k = 1;
 		while (k < amount) {
 			ZeroOnepark(k * val, k * vol);
 			amount -= k;
 			k <<= 1;
 		}
 		if (amount > 0)
 			ZeroOnepark(amount * val, amount * vol);
 	} 
}
int m;
int main(){
	while(~scanf("%d %d",&v,&n)){
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			scanf("%d %d",&c[i],&volume[i]);
		}
		for(int i=1;i<=n;i++){
			Multiplepark(volume[i],volume[i],c[i]);
		}
		
    	printf("%d\n",dp[v]);
	}
	
	return 0;
}