POJ-1384 完全背包

Memory 748K

Time 172MS

#include <iostream>
#include <cstring>

using namespace std;

int p[501];
int w[501];
int nums[10001];

int main()
{
    int times;
    cin >> times;
    for(int i = 0; i < times; ++i){
        int e,f;
        cin >> e >> f;
        int num = f - e;//硬币总重量
        int number;
        cin >> number;
        memset(p,0,sizeof(p));
        memset(w,0,sizeof(w));
        memset(nums,0,sizeof(nums));
        for(int j = 0; j < number; ++j){
           cin >> p[j] >> w[j];
        }
        nums[0] = 0;
        for(int j = 1; j <= num; ++j){
            nums[j] = 10000000;
        }
        for(int j = 0; j < number; ++j){
            for(int k = w[j]; k <= num; ++k){
                nums[k] = min(nums[k-w[j]]+p[j],nums[k]);
            }
        }
        if(nums[num] == 10000000){
            cout << "This is impossible." << endl;
        }else
            cout << "The minimum amount of money in the piggy-bank is " << nums[num] << "." << endl;
    }
    return 0;
}

POJ-1384 完全背包

原文：http://blog.csdn.net/lane_l/article/details/44652831