hdu3591The trouble of Xiaoqian 多重背包+全然背包

hdu3591The trouble of Xiaoqian 多重背包+全然背包

//给出Xiaoqian的钱币的价值和其身上有的每种钱的个数
//商家的每种钱的个数是无穷,xiaoqian一次最多付20000
//问如何付钱交易中钱币的个数最少
//Xiaoqian是多重背包
//商家是全然背包
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = 20010 ;
const int inf = 0x3f3f3f3f ;
int dp[maxn] ;
int dp_1[maxn] ;
int c[maxn],v[maxn] ;
int n , t ;int cas = 0 ;
int main()
{//freopen(&#" ,"r" , stdin) ;while(scanf("%d%d",&n , &t) &&(n+t)){for(int i = 1;i <= n;i++)scanf("%d" , &v[i]) ;for(int i = 1;i <= n;i++)scanf("%d" , &c[i]) ;for(int i = 1;i < maxn;i++)dp[i] = dp_1[i] = inf ;dp_1[0] = 0 ; dp[0] = 0 ;for(int i = 1;i <= n;i++)for(int j = v[i] ; j < maxn ;j++)dp_1[j] = min(dp_1[j], dp_1[j-v[i]] + 1) ;for(int i = 1;i <= n;i++){for(int k = 1;k <= c[i];k*=2){for(int j = maxn - 1;j >= k*v[i];j--)dp[j] = min(dp[j] , dp[j-k*v[i]] + k) ;c[i]-=k;}for(int j = maxn-1;j >= c[i]*v[i];j--)dp[j] = min(dp[j] , dp[j - c[i]*v[i]] + c[i]) ;}int ans = inf;for(int i = t; i <= maxn -10;i++)if(dp[i] != inf && dp_1[i - t] != inf)ans = min(dp[i] + dp[i-t] , ans) ;printf("Case %d: " ,++cas) ;if(ans == inf)puts("-1") ;else cout<<ans<<endl;}
}

转载于:.html