POJ 1276 Cash Machine 解答

题目详见: http://poj.org/problem?id=1276

这道题与POJ 1014同属一类题, 区别在于POJ 1014的解是求恰好等于容量的情况, 而这道题较为常规, 同时这道题的数据较大, 套用我在博客http://blog.csdn.net/hfut_jf/article/details/18190521里写的程序会出现Time Limit Exceeded错误, 必须加以优化, 先贴出原先的程序, 在与最后AC的代码比较, 主要看代码如何改进:

改进前代码(会出现Time Limit Exceeded错误):

#include <iostream>
using namespace std;
const int n=1001;
int main(int argc, char * argv[])
{
    int cash=0, N=0;
	int num[n]; // 每种面值钞票张数
	int d[n]; // 每种钞票对应面值
	int v[100001]; // 背包容量 
	int w[100]; // 压缩用数组

    memset(num, 0, sizeof(num));
    memset(d, 0, sizeof(d));
    while(true){
        // 初始化
        memset(v, 0, sizeof(v));
        
        cin>>cash>>N;
        for(int i=0;i<N;++i){
			cin>>num[i]>>d[i];
		}
		int k=0; // 记录压缩后替代物品数 
		// 二进制压缩
		for(int i=0;i<N;++i){
            int t=1;
            while(num[i]>0){
                if(num[i]>t){
                    num[i]-=t;
                    w[k++]=t*d[i];
                    t*=2;
                }else{
                    w[k++]=num[i]*d[i];
                    num[i]=0;      
                }        
            }
        }
        
        // 执行动态规划算法
        for(int i=0;i<k;++i){
            for(int j=cash;j>=w[i];--j){  
                if(v[j]<v[j-w[i]]+w[i])
                    v[j]=v[j-w[i]]+w[i];
            }
        }
        cout<<v[cash]<<endl; 
    }
    return 0;   
}

#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
    int cash=0, N=0;
	int num[1001];
	int d[1001];
	int v[100001];
    while(cin>>cash>>N){
        memset(v, 0, sizeof(v)); 
        for(int i=0;i<N;++i){
			cin>>num[i]>>d[i];
		    int w=0,t=1;
            while(num[i]>0){
                if(num[i]>t){
                    num[i]-=t;
                    w=t*d[i];
                    t*=2;
                }else{
                    w=num[i]*d[i];
                    num[i]=0;      
                }
                for(int j=cash;j>=w;--j){  
                    if(v[j]<v[j-w]+w)
                        v[j]=v[j-w]+w;
                }        
            } 
        }
        cout<<v[cash]<<endl; 
    }
    return 0;   
}

在一种币值钞票输入后即进行二进制压缩和动态规划计算, 减少了循环次数及所需存储空间.