POJ 1276 Cash Machine（多重背包模板）

多重背包模板：

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[100009];int a[20];int num[1009];

int main(){
	int al;
	while(cin>>al){
		int n;cin>>n;
		int m,x;int cnt=1;
		for(int i=1;i<=n;i++){
			scanf("%d%d",&m,&x);
		int j=1;//初始要分解成的数为1
		while(m>=j){
			a[cnt++]=j*x;//分解
			m-=j;//减掉已经分解的部分
			j*=2;
		}
		a[cnt++]=m*x;	//把剩下的加进数组
		}
		cnt--;
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=cnt;i++){
				for(int v=al;v>=a[i];v--){
					dp[v]=max(dp[v],dp[v-a[i]]+a[i]);
				}
		}
		cout<<dp[al]<<endl;
	}
}

朴素想法的多重背包：

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[100009];int a[20];int num[1009];

int main(){
	int al;
	while(cin>>al){
		int n;cin>>n;
		for(int i=1;i<=n;i++){
			scanf("%d%d",&num[i],&a[i]);
		}
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			for(int k=0;k<num[i];k++){
				for(int v=al;v>=a[i];v--){
					dp[v]=max(dp[v],dp[v-a[i]]+a[i]);
				}
			}
		}
		cout<<dp[al]<<endl;
	}
}

orz：网上的代码都好繁琐