随笔-141  评论-9  文章-3  trackbacks-0
设要付的钱是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]+< 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]+< 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 小阮 阅读(302) 评论(0)  编辑 收藏 引用 所属分类: POJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理