题目描述
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 \leq H \leq 50000)H(1≤H≤50000) 磅干草。
他知道 N(1 \leq N\leq 100)N(1≤N≤100) 个干草公司,现在用 11 到 NN 给它们编号。
第 ii 公司卖的干草包重量为 P_i (1 \leq P_i \leq 5,000)P i(1≤P i≤5,000) 磅,
需要的开销为 C_i(1\leqC_i\leq5,000)Ci(1≤Ci ≤5,000) 美元。每个干草公司的货源都十分充足, 可以卖出无限多的干草包。
帮助约翰找到最小的开销来满足需要,即采购到至少 HH 磅干草。
样例
2 15
3 2
5 3
输出1
9
分析
这是一个背包问题 不过这个状态设置 f[j] 表示体积至少为j的价值
如何体现这个至少呢 就是 枚举的时候从0 到 最大值
如果当前的体积装不下也无所谓,加进去只要他能是价值变小就行
(动态规划) $O(HN)$
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5;
int f[N];
int V,n,w,v;
int main()
{
//至少H捆干草
cin >> n >> V;
memset(f,0x3f,sizeof f);
f[0] = 0;
while(n --)
{
cin >> v >> w;
for(int j = 0;j <= V;j ++)
f[j] = min(f[j],f[max(j - v,0)] + w);
}
cout << f[V];
return 0;
}
太卷了
卧槽了,咋发现我的,东哥