用普通的多重背包会TLE.
优化如下:
//这道题主要是由于cost 和 weight 是一样的,而且只问是否可以凑到该数. //将dp数组设为bool类型,只要可以达到,便记为1,否则为0. //初始条件是dp[0] = 1;表示0 dollars 总是可以凑出的~ //转移方程是 dp[i] |= dp[i-A[i]];表示对于前i个面值的所有硬币, //总钱数i可以凑出的条件: // 1.对于前i-1或i(分别对应01背包和完全背包)个面值的所有硬币,可以凑出i的总钱数 //或 // 2.对于前i-1个面值的所有硬币,可以凑出i-A[i]总钱数 //Memory: 348K Time: 2766MS!! #include <iostream> #include <cstring> using namespace std; const int MAXN = 105; const int MAXM = 100005; int A[MAXN],C[MAXN],v; bool dp[MAXM]; void ZeroOnePack(int cost) { for(int i=v;i>=cost;i--) if(!dp[i]) dp[i] = dp[i-cost]; return; } void CompletePack(int cost) { for(int i=cost;i<=v;i++) if(!dp[i]) dp[i] = dp[i-cost]; return; } void MultiplePack(int cost, int amount) { if(cost*amount>=v) CompletePack(cost); else { int k = 1; while(k<=amount) { ZeroOnePack(k*cost); amount -= k; k *= 2; } ZeroOnePack(amount*cost); return; } } int main() { int n,m; while(cin>>n>>m && (n+m)) { for(int i=1;i<=n;i++) cin>>A[i]; for(int i=1;i<=n;i++) cin>>C[i]; memset(dp,0,sizeof(dp)); dp[0] = 1; v = m; int cnt = 0; for(int i=1;i<=n;i++) { if(C[i]) MultiplePack(A[i],C[i]); } for(int i=1;i<=m;i++) { if(dp[i]) cnt++; } cout<<cnt<<endl; } return 0; }
虽然内存还好,但是时间依旧长..我又百度了另一种优化方法:
//Memory: 460K Time: 1172MS #include<cstdio> #include<cstring> using namespace std; bool dp[100005]; int p[105]; short c[105]; short num[100005]; int main() { int i,j,n,m,cnt; while(scanf("%d%d",&n,&m),n+m) { for(i=0;i<n;i++) scanf("%d",&p[i]); for(i=0;i<n;i++) scanf("%hd",&c[i]); memset(dp,0,sizeof(dp)); dp[0]=1; cnt=0; //当做完全背包,对取的物品数通过另一个dp进行限制,减少了调用函数的过程 //算是对多重背包的另一种优化思路吧,beside binary for(i=0;i<n;i++) { memset(num,0,sizeof(num)); for(j=p[i];j<=m;j++) { if(!dp[j]&&dp[j-p[i]]&&num[j-p[i]]<c[i])//双线dp啊..num也有状态转移方程 { num[j]=num[j-p[i]]+1;//num[j]表示总钱数为j时选择i种硬币的个数 dp[j]=1; cnt++; } } } printf("%d\n",cnt); } return 0; }
但是..status中的前几名...