Buying Hay S（洛谷）

题解完全背包（优化2.0）：#include <iostream>#include <cstring>using namespace std;const int N = 110, M = 100010;int n, m;int v[N], w[N], f[M];int main(){cin >> n >> m;for (int i = 1; i &l

业余算法学徒

154人浏览 · 2020-10-03 21:44:08

业余算法学徒 · 2020-10-03 21:44:08 发布

题目翻译
约翰的干草库存已经告罄，他打算为奶牛们采购 H 磅干草，他知道 N 个干草公司，现在用 1 到 N 给它们编号。

第 i 公司卖的干草包重量为 P_i 磅，需要的开销为 C_i 美元，每个干草公司的货源都十分充足，可以卖出无限多的干草包。

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

输入格式
第 1 行：两个用空格分隔的整数: N 和 H
第 2 ~ n+1 行：每行包含两个空格分隔的整数: P_i 和 C_i

输出格式
一个整数，代表约翰获得至少 H 磅干草所需的最低成本。

输入样例
2 15
3 2
5 3

输出样例
9

说明/提示
约翰可以从第二个供应商那里购买三个包装，总成本为 9 英镑。

题解
完全背包（优化2.0）：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110, M = 100010;

int n, m;
int v[N], w[N], f[M];

int main()
{
	cin >> n >> m;
	
	for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
	
	memset(f, 0x3f, sizeof f);
	
	f[0] = 0;
	for (int i = 1; i <= n; i ++)
		for (int j = v[i]; j <= m * 2; j ++)
			f[j] = min(f[j], f[j - v[i]] + w[i]);
			
	int ans = 0x3f3f3f3f;
	for (int i = m; i <= m * 2; i ++) ans = min(ans, f[i]);
	
	cout << ans << endl;
	return 0;		
}