P2918 [USACO08NOV] Buying Hay S

题目描述

Farmer John is running out of supplies and needs to purchase H (1 <= H <= 50,000) pounds of hay for his cows.

He knows N (1 <= N <= 100) hay suppliers conveniently numbered 1..N. Supplier i sells packages that contain P_i (1 <= P_i <= 5,000) pounds of hay at a cost of C_i (1 <= C_i <= 5,000) dollars. Each supplier has an unlimited number of packages available, and the packages must be bought whole.

Help FJ by finding the minimum cost necessary to purchase at least H pounds of hay.

约翰的干草库存已经告罄，他打算为奶牛们采购 $H(1\le H\le 50000)$ 磅干草。

他知道 $N(1\le N\le 100)$ 个干草公司，现在用 $1$ 到 $N$ 给它们编号。第 $i$ 公司卖的干草包重量为 $P_i(1\le P_i\le 5,000)$ 磅，需要的开销为 $C_i(1\le C_i\le 5,000)$ 美元。每个干草公司的货源都十分充足， 可以卖出无限多的干草包。

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

输入格式

* Line 1: Two space-separated integers: N and H

* Lines 2..N+1: Line i+1 contains two space-separated integers: P_i and C_i

输出格式

* Line 1: A single integer representing the minimum cost FJ needs to pay to obtain at least H pounds of hay.

说明/提示

FJ can buy three packages from the second supplier for a total cost of 9.

思路

完全背包，找最小成本，如果把干草重量视为价值，金额视为物品重量，那容量dp的时候不知道多少合适，因为没有确切的上限

先考虑把H视为背包的容量，找到H和H+5000（单个最大5000磅）之间最小值

题解

#include <iostream>
#include <cstring>
#define debug(x) #x << ":" << x << " "

using namespace std;

struct
{
    int weight;
    int cost;
} hay[128];

int dp[55020];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, H;
    cin >> N >> H;
    
    memset(dp,0x3f3f3f3f,sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= N; i++)
    {
        cin >> hay[i].weight >> hay[i].cost;
    }

    for (int i = 1; i <= N; i++)
    {
        for (int j = hay[i].weight; j <= H + 5000; j++)
        {
            dp[j] = min(dp[j],dp[j - hay[i].weight] + hay[i].cost);
        }
    }

    int minc = dp[H];
    for (int j = H + 1; j <= H + 5000;j++)
    {
        // cout << debug(dp[j]);
        minc = min(minc, dp[j]);
    }

    cout << minc;
    return 0;
}