HDU1114 存钱罐 完全背包

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1114

给你一个存钱罐的空的质量和存满钱的质量，给你每种硬币的质量和价值，让你算出它的最小价值。

  
  

   
   3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
  
  

  
  

   
   The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
  
  

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[505][10005];
const int inf = (1 << 30) - 1;
int main()
{
    int T,n,i,v,w,l,h,j;
    int p[505], m[505];
    cin >> T;
    while (T--)
    {
        cin >> l >> h>>n;
        h -= l;
        memset(p, 0, sizeof(p));
        memset(m, 0, sizeof(m));
        for (i = 0; i < n; i++)
            cin >> p[i] >> m[i];
        for (i = 0; i <=n; i++)
        {
            for (j = 0; j <= h; j++)
            {
                if ( j == 0)
                    dp[i][j] = 0;
                else dp[i][j] = inf;
            }
        }
        for(i=0;i<n;i++)
        {
            for ( j = 0; j <=h; j++)
            {
                    if (m[i] > j)
                        dp[i + 1][j] = dp[i][j];
                    else
                    dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - m[i]] + p[i]);
            }
        }

        if (dp[n][h] == inf)printf("This is impossible.n");
        else
            printf("The minimum amount of money in the piggy-bank is %d.n", dp[n][h]);
    }
    return 0;
}

最后

以上就是醉熏月饼为你收集整理的HDU1114 存钱罐 完全背包的全部内容，希望文章能够帮你解决HDU1114 存钱罐 完全背包所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。