首页 > ACM题库 > HDU-杭电 > HDU 3591-The trouble of Xiaoqian-背包问题-[解题报告]HOJ
2014
11-27

HDU 3591-The trouble of Xiaoqian-背包问题-[解题报告]HOJ

The trouble of Xiaoqian

问题描述 :

In the country of ALPC , Xiaoqian is a very famous mathematician. She is immersed in calculate, and she want to use the minimum number of coins in every shopping. (The numbers of the shopping include the coins she gave the store and the store backed to her.)
And now , Xiaoqian wants to buy T (1 ≤ T ≤ 10,000) cents of supplies. The currency system has N (1 ≤ N ≤ 100) different coins, with values V1, V2, …, VN (1 ≤ Vi ≤ 120). Xiaoqian is carrying C1 coins of value V1, C2 coins of value V2, …., and CN coins of value VN (0 ≤ Ci ≤ 10,000). The shopkeeper has an unlimited supply of all the coins, and always makes change in the most efficient manner .But Xiaoqian is a low-pitched girl , she wouldn’t like giving out more than 20000 once.

输入:

There are several test cases in the input.
Line 1: Two space-separated integers: N and T.
Line 2: N space-separated integers, respectively V1, V2, …, VN coins (V1, …VN)
Line 3: N space-separated integers, respectively C1, C2, …, CN
The end of the input is a double 0.

输出:

There are several test cases in the input.
Line 1: Two space-separated integers: N and T.
Line 2: N space-separated integers, respectively V1, V2, …, VN coins (V1, …VN)
Line 3: N space-separated integers, respectively C1, C2, …, CN
The end of the input is a double 0.

样例输入:

3 70
5 25 50
5 2 1
0 0

样例输出:

Case 1: 3

HDU 3591 The trouble of Xiaoqian(多重背包+完全背包)

http://acm.hdu.edu.cn/showproblem.php?pid=3591

题意:

       有一个具有n种货币的货币系统, 每种货币的面值为val[i]. 现在小杰手上拿着num[1],num[2],…num[n]个第1种,第2种…第n种货币去买价值为T(T<=20000)的商品, 他给售货员总价值>=T的货币,然后售货员(可能,如果小杰给的钱>T,那肯定找钱)找钱给他.
售货员每次总是用最少的硬币去找钱给小杰. 现在的问题是: 小杰买价值T的商品时, 他给售货员的硬币数目+售货员找他的硬币数目最少等于多少?

分析:

       我们令dp1[j]==x表示小杰给售货员价值j的硬币时, 需要最少x个硬币. 我们令dp2[j]==x表示售货员给小杰价值j的硬币时, 需要最少x个硬币.

       那么前一个问题就是一个多重背包问题(因为小杰的硬币有限度), 而第2个问题是完全背包问题(售货员硬币无限).

       最终我们所求为:  min( dp1[T+i]+dp2[i]) 其中 i属于[0,20000-T].

      

       对于第一个多重背包问题:

       我们令dp1[i][j]==x表示用前i种硬币构成j金钱时, 最少需要x个硬币.

       初始化: dp1全为INF且dp1[0][0]=0.

       对于第i种硬币, 我们要分情况处理:

       如果val[i]*num[i]>=20000, 那么就做一次完全背包.

       如果val[i]*num[i]<20000, 那么就把该物品看出新的k+1种物品,然后做k+1次01背包.

       最终我们所求为dp1[n][j]这维数组就是我们之前说的dp1[j].

      

       对于第二个完全背包问题:

       我们令dp2[i][j]==x表示用前i种硬币构成j金钱时, 最少需要x个硬币.

       初始化: dp2全为INF 且dp2[0][0]=0.

       状态转移: dp2[i][j] = min( dp2[i-1][j] , dp2[i][j-val[i]]+1 )     //sum是求和

       前者表示第i种货币一个都不用, 后者表示第i种货币至少用1个.

       最终所求: dp2[n][j]这维数组是我们上面所求的dp2[j].

 

       最终让i从T+1到20000遍历一边, 找出min( dp1[T] , dp1[i]+dp2[i-T] )的值.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 1e8
const int maxn=100+5;

int n;//n种货币
int T;//商品金额
int val[maxn];//每种货币面值
int num[maxn];//每种货币数目
int dp1[20000+5];
int dp2[20000+5];

//1次01背包过程
void ZERO_ONE_PACK(int *dp,int cost,int sum)
{
    for(int i=20000;i>=cost;i--)
        dp[i] = min(dp[i],dp[i-cost]+sum);//注意这里是+sum,而不是+1
}

//1次完全背包过程
void COMPLETE_PACK(int *dp,int cost)
{
    for(int i=cost;i<=20000;i++)
        dp[i] = min(dp[i],dp[i-cost]+1);
}

//1次多重背包过程
void MULTIPLY_PACK(int *dp,int cost,int sum)
{
    if(cost*sum>=20000)
    {
        COMPLETE_PACK(dp,cost);
        return ;
    }

    int k=1;
    while(k<sum)
    {
        ZERO_ONE_PACK(dp,cost*k,k);
        sum-=k;
        k*=2;
    }
    ZERO_ONE_PACK(dp,cost*sum,sum);
}

int main()
{
    int kase=0;
    while(scanf("%d%d",&n,&T)==2)
    {
        //注意退出,否则WA
        if(n==0 && T==0) break;

        //读取输入
        for(int i=1;i<=n;i++)
            scanf("%d",&val[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);

        //初始化
        for(int i=0;i<=20000;i++)
            dp1[i]=dp2[i]=INF;
        dp1[0]=dp2[0]=0;

        //递推
        for(int i=1;i<=n;i++)
            MULTIPLY_PACK(dp1,val[i],num[i]);
        for(int i=1;i<=n;i++)
            COMPLETE_PACK(dp2,val[i]);

        //输出结果
        int ans=dp1[T];
        for(int i=T+1;i<=20000;i++)
            ans=min(ans, dp1[i]+dp2[i-T]);

        printf("Case %d: %d\n",++kase,ans==INF?-1:ans);
    }
    return 0;
}

参考:http://blog.csdn.net/u013480600/article/details/40582487


  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3