HDU 1114 Piggy-Bank 猪仔储钱罐(AC代码)完全背包(容量需满,价值最小)

 1 #include <iostream>
 2 #define MAX 0xfffffff
 3 using namespace std;
 4 //要求:1、刚好装满    2、总价值最小
 5 int value[501];
 6 int weight[501];
 7 int dp[10010];
 8 int min(int a,int b)
 9 {
10     return a<b?a:b;
11 }
12 int cal(int v,int n)    //空间、种类
13 {
14     int i,j;
15     dp[0]=0;
16     for(i=1;i<=v;i++)
17         dp[i]=MAX;
18     for(i=1;i<=n;i++)
19         for(j=weight[i];j<=v;j++)
20         {
21                 dp[j]=min( dp[j] , dp[j-weight[i]] + value[i] );
22         }
23     return dp[v];
24 }
25 void main()
26 {
27     int T;
28     scanf("%d",&T);
29     int E,F,N,ans;
30     while(T--)
31     {
32         int i;
33         scanf("%d%d",&E,&F);    //空罐、满罐
34         scanf("%d",&N);            //多少种硬币
35         for(i=1;i<=N;i++)
36         {
37             scanf("%d%d",&value[i],&weight[i]);    //价值、重量
38         }
39         ans=cal(F-E,N);
40         if(ans==MAX)
41             printf("This is impossible.\n");
42         else
43             printf("The minimum amount of money in the piggy-bank is %d.\n",ans);
44     }
45 }

1114

题意:给定一个存钱罐中要存硬币,知道空罐的重量和欲装满的重量,是否能装入?若能,打印最小价值。(注:能装的硬币重量一定刚刚好,里面的总价值要达到最小)

输入:包含了T个测试例子,在第一行给出。接下来有T个例子,每个例子第一行包括两整数E和F,分别代表空罐的重量和装满钱的重量,单位都为克。 1 <= E <= F <= 10000. 第二行包含了一个整数N,代表了硬币的种类。(1 <= N <= 500)接下来N行是N种硬币的信息,每行有两个整数P和W,分别代表价值和重量,单位是克。

输出:每例输出一行,若能装入,打印The minimum amount of money in the piggy-bank is X. 其中X是钱的总额。若不能装入,打印 This is impossible.

思路:和完全背包一样,不同的是硬币的重量要恰好,不能多或少,总价值要最小,这与完全背包问题相反。需要特别地处理这两个问题,重量要恰好,那么在更新dp的时候要保证这一点,总价要最小,那么在比较的时候要用min而不是max了。

时间: 01-17

HDU 1114 Piggy-Bank 猪仔储钱罐(AC代码)完全背包(容量需满,价值最小)的相关文章

hdu 1114 基础完全背包

题意:给一个储钱罐,已知空的储钱罐和装了硬币的储钱罐的质量.然后给了n种硬币的质量和价值. 问储钱罐里最少有多少钱. 解法:完全背包.注意要初始化为 INF,要正好装满,如果结果是INF,输出This is impossible. 1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #includ

[2016-03-27][HDU][1114][Piggy-Bank]

时间:2016-03-27 16:37:56 星期日 题目编号:[2016-03-27][HDU][1114][Piggy-Bank] 遇到的问题:注意f == e的情况,即dp[0] = 0; #include <cstring> #include <cstdio> #include<algorithm> using namespace std; int dp[10000 + 10]; int w[500 + 10],c[500 + 10]; int main(){

hdu 1114 Piggy-Bank

题目: 链接:点击打开链接 题意: 知道存钱罐的质量和装满硬币的存钱罐的质量,然后是不同硬币的价值和质量,求出存钱罐里钱币的最小价值. 算法: 完全背包问题,银币的个数是不限的. 思路: 状态转移方程:j = 0时,价值为0 dp[j] = min(dp[j],dp[j-w[i]]+v[i]);//表示质量为j的钱币,含有的最小的价值 代码: #include<iostream> #include<cstdio> #include<cstring> using name

hdu 1114 完全背包问题

题意:给定背包体积与物品的体积与价值 求正好放完的最小价值#include<iostream> using namespace std; int min(int a,int b) { if(a<b) return a; return b; } int main() { int t,m1,m2,n,i,j; int v[502],w[502],dp[10005],m; cin>>t; while(t--) { cin>>m1>>m2; m=m2-m1;

HDU 1114 Piggy-Bank(一维背包)

题目地址:HDU 1114 把dp[0]初始化为0,其它的初始化为INF.这样就能保证最后的结果一定是满的,即一定是从0慢慢的加上来的. 代码例如以下: #include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #incl

hdu 1548 (dijkstra解法)(一次AC就是爽)

恭喜福州大学杨楠获得[BestCoder Round #4]冠军(iPad Mini一部) <BestCoder用户手册>下载 A strange lift Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 11670    Accepted Submission(s): 4430 Problem Description There is

hdu 1028 Ignatius and the Princess III(母函数,完全背包)

http://acm.hdu.edu.cn/showproblem.php?pid=1028 整数划分问题. 第一道母函数...母函数入门 小于等于n的整数共有n个,1,2......n,每个数都有无限多个,对于整数1,它所对应的母函数为(1+x+x^2+...+x^k+...),整数2对应的母函数为(1+x^2+X^4+...+x^(2*k)+...),整数3对应的母函数为(1+x^3+x^6+...+x^(3*k)+...),以此类推,直到整数n. 那么n的整数划分的个数就是这n个母函数乘积

HDU 4738 Caocao&#39;s Bridges(求价值最小的桥)

Problem Description Caocao was defeated by Zhuge Liang and Zhou Yu in the battle of Chibi. But he wouldn't give up. Caocao's army still was not good at water battles, so he came up with another idea. He built many islands in the Changjiang river, and

hdu 1114 Piggy-Bank 完全背包

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1114 题意分析:给出存钱罐存钱前后的重量,以及钱的种类及其价值和种类, 要求装满存钱罐最小的价值.  完全背包 /*Piggy-Bank Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13578 Accepted Submission(s):