题目

题目大意

约翰的干草库存已经告罄，他打算为奶牛们采购 磅干草。

他知道 个干草公司，现在用 到 给它们编号。第 公司卖的干草包重量为 磅，需要的开销为 美元。每个干草公司的货源都十分充足， 可以卖出无限多的干草包。

帮助约翰找到最小的开销来满足需要，即采购到至少 磅干草。

输入格式

第 1 行：两个空格分隔的整数： 和

第 2~N+1 行：第 i+1 行包含两个空格分隔的整数： 和

输出格式

一个整数，表示 FJ 为获得至少 H 磅干草所需的最低成本。

样例 #1

样例输入 #1

2 15 
3 2 
5 3

样例输出 #1

9

提示

FJ可以从第二个供应商处购买三包，总费用为9

解答

思路

该题为完全背包（不限草垛数量），采用一维滚动数组，因为此题开的数组比较大二维数组浪费空间（一些废话）。

状态转移方程 , 其中 指供应商的编号，指干草的重量，dp[j] 表示 购买j磅干草所耗费的成本。

需要注意的是，题目中指出 purchase at least H pounds of hay.求出购买至少 H 磅干草所需的最低成本。 故干草的重量可以超过H磅。

参考代码

#include <iostream>
using namespace std;

int ans=1e9,N,H,P[101],C[101],dp[55001]; 

int main() {
    cin >> N >> H;
    for (int i = 1; i <= N; ++i) {
        cin >> P[i] >> C[i];
    }

//  初始化
    dp[0] = 0; // 非常重要的一步！在求解只购入一包干草的时候会用到
    for (int i = 1; i <= 55000; ++i) {
        dp[i] = 1e9; // 初始化为无穷大
    }

//  递推求解：完全背包-一维滚动数组
    for (int i = 1; i <= N; ++i) {
        for (int j = P[i]; j <= H + 5000; ++j) {
                dp[j] = min(dp[j], dp[j - P[i]] + C[i]);
        }
    }
    
//  finding the minimum cost necessary to purchase at least H pounds of hay. 求出购买至少 H 磅干草所需的最低成本。
    for (int i = H; i <= H + 5000; ++i) {
        ans = min(ans,dp[i]);
    }
    
    cout<<ans<<endl;
    return 0;
}