題意

給n個幣的價值和其數量，問能組合成\(1-m\)中多少個不同的值。

分析

對\(c[i]*a[i]>=m\)的幣，相當于完全背包；\(c[i]*a[i]<m\)的幣則是多重背包，考慮用二進制優(yōu)化解決。最后掃一遍\(dp[i]\)統計答案。

import java.util.*; import java.math.*;public class Main{static int MAXN = 100005;static int []dp = new int[MAXN];static int []a = new int [MAXN];static int []c = new int [MAXN];static int n,m;static void zero(int w,int v) {for(int i=m;i>=w;--i) {dp[i] = Math.max(dp[i], dp[i-w]+v);}}static void complete(int w,int v) {for(int i=w;i<=m;++i) {dp[i] = Math.max(dp[i], dp[i-w]+v);}}static void multiple(int w,int v,int c) {if(c * w >= m) {complete(w,v);return;}int k = 1;while(k<=c) {zero(k*w,k*v);c -= k;k <<= 1;}zero(c*w,c*v);}public static void main(String []args) {Scanner cin = new Scanner (System.in);while(cin.hasNext()) {n = cin.nextInt();m = cin.nextInt();if(n==0 && m==0) break;for(int i=0;i<=m;++i) dp[i]=-1;dp[0] = 0;for(int i=1;i<=n;++i) {a[i] = cin.nextInt();}for(int i=1;i<=n;++i) {c[i] = cin.nextInt();multiple(a[i],a[i],c[i]);}int res=0;for(int i=1;i<=m;++i) {if(dp[i]==i) {res++;}}System.out.println(res);}cin.close();} }

轉載于:https://www.cnblogs.com/xiuwenli/p/9827669.html

總結

以上是生活随笔為你收集整理的HDU - 2844 Coins(多重背包+完全背包)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。