cash to cash cycle，Cash Machine POJ - 1276

解法

多重背包板子題

多重背包板子

如果上限的體積大于了給定的體積那么套完全背包

否則二進制優化成01背包

代碼

#include <iostream>
#include <cstring>
using namespace std;
int dp[100005],m;
void zb(int v,int w)
{for(int i=m;i>=v;i--)dp[i]=max(dp[i],dp[i-v]+w);
}
void cb(int v,int w)
{for(int i=v;i<=m;i++)dp[i]=max(dp[i],dp[i-v]+w);
}
void mb(int v,int w,int n)
{if(v*n>=m){cb(v,w);return;}int k=1;while(k<n){zb(k*v,k*w);n-=k;k*=2;}zb(n*v,n*w);
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);while(cin>>m){int n;cin>>n;memset(dp,0,sizeof(dp));for(int i=0;i<n;i++){int v,w,n;cin>>n>>v;mb(v,v,n);}cout<<dp[m]<<"\n";}
}