存钱罐
题目：
代码如下：
#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]不等于最大值那就证明可以凑出，否则输出不可能。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！