存钱罐

题目：


代码如下：

#include
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]不等于最大值那就证明可以凑出，否则输出不可能。