POJ1276:Cash Machine(多重背包)
题目:http://poj.org/problem?id=1276
多重背包模板题,没什么好说的,但是必须利用二进制的思想来求,否则会超时,二进制的思想在之前的博客了有介绍,在这里就不多说了。
#include <iostream> #include <string.h> #include <stdio.h> #include <algorithm> #include <math.h> using namespace std; int V,n,w[20],cnt[20],dp[1000010]; void com(int v) { for(int i=v; i<=V; i++) { dp[i]=max(dp[i],dp[i-v]+v); } return ; } void one(int v) { for(int i=V;i>=v;i--) { dp[i]=max(dp[i],dp[i-v]+v); } return ; } int main() { while(scanf("%d",&V)!=EOF) { scanf("%d",&n); for(int i=0; i<n; i++) { scanf("%d%d",&cnt[i],&w[i]); } memset(dp,0,sizeof(dp)); for(int i=0; i<n; i++) { if(cnt[i]==0) continue; if(cnt[i]*w[i]>=V) { com(w[i]); } else { int t=1; while(t<cnt[i]) { one(w[i]*t); cnt[i]-=t; t<<=1; } one(w[i]*cnt[i]); } } printf("%d\n",dp[V]); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。