设要付的钱是M，存在一个付钱的上限V，对于0到V是一个多重背包问题（每种货币有限制数量）
对于给多的部分， 即V－M，由于还钱时候，每种货币没有数量限制，是一个完全背包问题。
参考这篇文章，
http://www.cppblog.com/Davidlrzh/articles/135614.html证明了，V 最大为 M + v[i]*v[i] （v[i]是货币中最大价值的一个）
#include <iostream>
using namespace std;
const int MAXN = 25000;
const int MAX = 105;
const int INF = 99999;
int v[MAX], n[MAX];
int f[MAXN], g[MAXN];
int V,N;
void ZeroOnePack(int c, int w, int dp[])
{
for(int v=V; v>=c; --v)
if(dp[v-c]+w < dp[v])
dp[v] = dp[v-c]+w;
return;
}
void CompletePack(int c, int w, int dp[]){
for(int v=c; v<=V; ++v)
if(dp[v-c]+w < dp[v])
dp[v] = dp[v-c]+w;
return;
}
void MultiplePack(int c, int w, int m, int dp[]){
if(m*c>=V){
CompletePack(c, w, dp);
return;
}
int k=1;
while(k<m){
ZeroOnePack(k*c, k, dp);
m-=k;
k*=2;
}
ZeroOnePack(m*c, m, dp);
}
int M;
int main(){
int i, max=0;
cin>>N>>M;
for(i=1; i<=N; ++i){
cin>>v[i];
if(v[i]>max)
max=v[i];
}
for(i=1; i<=N; ++i)
cin>>n[i];
V = M + max*max;
for(i=1; i<V; ++i)
f[i] = INF;
for(i=1; i<=N; ++i)
MultiplePack(v[i], 1, n[i], f);
V = max*max;
for(i=1; i<V; ++i)
g[i] = INF;
for(i=1; i<=N; ++i)
CompletePack(v[i], 1, g);
V = M+max*max;
int min = INF;
for(i=M; i<V; ++i)
if(f[i]+g[i-M]<min)
min = f[i]+g[i-M];
if(min!=INF)
cout<<min<<endl;
else
cout<<-1<<endl;
return 0;
}
posted on 2010-12-23 13:10
小阮 阅读(292)
评论(0) 编辑 收藏 引用 所属分类:
POJ