Description

 

Oliver分别有币值为1，3，5，7，9，13元的硬币a，b，c，d，e，f枚。一天她去大学生超市买糖吃，糖的价格为g元。

问：用Oliver仅有的这6种硬币去恰好购买这g元的糖果，最少需要支付多少个硬币？（当不能支付时输出“impossible”）

 

Input

 

输入数据有多组（当输入连续的7个零时，结束。该组数据不做处理）

每组数据依次输入币值为1，3，5，7，9，13元的硬币的个数，以及糖果的价格g。

 

Output

 

输出数据有多组，每组数据一行，为需要支付的最少硬币个数。

 

Sample Input

 

1 1 0 0 0 0 10

1 1 1 1 1 1 38

0 0 0 0 0 0 0

Sample Output

impossible

6

题意很简单，暴力不可以

要用dp背包

我们可以先想下简单的01背包就是倒着来少一层循环的，就像这样

先循环容量和价值，这样就能只放一次，然后就是从大往小背，如果从小往大，那么一个东西可能会被多加（就是可重复选择）

(01背包求选任意个的最大价值) #include
       
        #include
        
         #include
         
          using namespace std;int vol[1005],price[1005],dp[1005];int main(){    //freopen("1.in", "r",stdin);    int T;    cin>>T;    while(T--)    {        int n,m;        cin>>n>>m;        for(int i=0;i
          
           >price[i];        for(int i=0;i
           
            >vol[i];        memset(dp,0,sizeof(dp));        for (int i = 0; i < n; i++) {            for (int j = m; j >=vol[i]; j--) {                dp[j] = max(dp[j - vol[i]] + price[i], dp[j]);            }        }        cout<
            
             <<"\n"; }}
            
           
          
         
        
       

而这个题目其实就相当于对背包的数量进行扩充，其实也等于让他再背硬币枚数次，当然你也可以把它全加在里面。

#include 
        
         #include 
         
          #include 
          
           using namespace std ;const int a[8]={
      0,1,3,5,7,9,13},INF=1e9;int b[8];int dp[100005];int   main(){int m ,num ;while(~scanf("%d%d%d%d%d%d%d",&b[1],&b[2],&b[3],&b[4],&b[5],&b[6],&m)){  int s=m;   for(int i=1;i<7;i++)   s+=b[i];   if(s==0)break;   for(int i=1;i<=m;i++)   dp[i] = INF;   for(int i = 1 ;i <= 6; i++)       for(int j = 1 ; j <= b[i] ; j++)           for(int  k = m ; k >= a[i] ;  k-- )           {               dp[k] = min(dp[k-a[i]] +1,dp[k]);           }   if(dp[m]==INF)printf("impossible\n");   else printf("%d\n",dp[m]);}return 0 ;}