王道机试指南 例题12.8 Piggy-Bank

题目：

题目大意：

算法梳理：

这是一道“背包问题”的应用。“背包问题”分为“0-1背包问题”和“完全背包问题”。

• 0-1背包问题

• 完全背包问题

本题思路：

代码：

#include <iostream>
#include <ostream>

using namespace std;

const int MAXN=10000;

int main(){
    int t;
    cin>>t;
    for(int k=0;k<t;k++){
        int e,f;
        cin>>e>>f;
        int m=f-e;//相当于背包总重量
        int n;
        cin>>n;//相当于物品件数
        int v[n],w[n];//相当于每件物品的价值和重量
        for(int i=0;i<n;i++)
            cin>>v[i]>>w[i];

        int dp[m+1];
        dp[0]=0;//dp[0]初始化为0
        for(int j=1;j<=m;j++)//由于所求为最小值，其他dp[i]初始化为正无穷
            dp[j]=MAXN;

        for(int i=0;i<n;i++)
            for(int j=w[i];j<=m;j++)
                dp[j]=min(dp[j],dp[j-w[i]]+v[i]);//状态转移方程

        if(dp[m]==MAXN)
            cout<<"This is imppossible."<<endl;
        else
            cout<<"The minimum amount of money in the piggy-bank is "<<dp[m]<<"."<<endl;
    }
    return 0;
}

运行结果：