本文共 1577 字，大约阅读时间需要 5 分钟。

Dawn-K recently discovered a very magical phenomenon in the supermarket of Northeastern University: The large package is not necessarily more expensive than the small package.

On this day, Dawn-K came to the supermarket to buy mineral water, he found that there are nn types of mineral water, and he already knew the price pp and the weight cc (kg) of each type of mineral water. Now Dawn-K wants to know the least money aa he needs to buy no less than mm kilograms of mineral water and the actual weight bb of mineral water he will get. Please help him to calculate them.

Input

Output

Examples

样例输入

Hint

题意:

超市有n种水, 每种水有价格p[i]和c[i]升2个属性, 求问至少买m升的水最少花多少钱和实际买到水的数量, 如果有多个价格一致的方案, 则输出买的水更多的

题解:

首先2个属性, 一个容量要想到背包, 再看到每种水不限数量, 应该想到完全背包问题.

经验小结:

#include
   
    using namespace std;#define ms(x, n) memset(x,n,sizeof(x));typedef  long long LL;const int inf = 1 << 30;const int maxn = 5e4+10;const int maxm = 2e4;int n, m, c[maxn], w[maxn];LL dp[maxm<<1];int main() {
       while(cin >> n >> m){
           for(int i = 1; i <= n; ++i)            cin >> w[i] >> c[i];        for(int i = 1; i <= maxm; ++i)            dp[i] = LONG_LONG_MAX/2;        dp[0] = 0;        for (int i = 1; i <= n; i++)            for (int j = c[i]; j <= maxm; j++)                dp[j] = min(dp[j], dp[j - c[i]] + w[i]);        LL a = LONG_LONG_MAX, b = 0;        for(int i = m; i <= maxm; ++i)            if(dp[i] <= a)                a = dp[i], b = i;        cout << a << ' ' << b << endl;    }    return 0;}
   

转载地址：https://suprit.blog.csdn.net/article/details/100836595 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！