存钱罐

　

存钱罐

题目：

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define NIL 0x3f3f3f3f
int p[505],w[505],dp[10005];//dp[i]:重量为i时最小价值 
int main()
{
	int n,e,f,v;
	cin >> e >> f;
	cin >> n;
	memset(dp,NIL,sizeof(dp));
	v = f - e;
	dp[0] = 0;
	for(int i = 0;i < n;i++) cin >> p[i] >> w[i];
	for(int i = 0;i < n;i++)
		for(int j = w[i];j <= v;j++)
			dp[j] = min(dp[j],dp[j - w[i]] + p[i]);
	if(dp[v] != NIL) cout << dp[v];
	else cout << "impossible." << endl;
	return 0;
}

这是一道完全背包问题，这里要正好凑够重量，所以先将dp[i]赋值为最大值，每次选取较小的那个，如果最后dp[v]不等于最大值那就证明可以凑出，否则输出不可能。

相关阅读