多重背包问题的两种O(M*N)解法
多重背包的题目很多,最著名的是poj1742楼教主的男人八题之一。
poj1742:coins
有几种面值的钱币和每种的数量,问能够组成m以内的多少种钱数
这个题大家都归为多重背包问题,不过跟实际意义上的背包还是有所差别的
因为如果把钱币看作背包中的物品,那么这个物品的价值和重量是相等的。
也就是没有“性价比"的。。
一种比较快速简单的做法是:
在判断能否放满某个体积时,如果能放满,尽量少用当前物品,贪心一下,对当前物品最优即可。
也可以用dp的思路想,就是dp[i][j]保存 j 体积最少用多少个物品 i
状态转移很明显:如果 dp[i-1][j] 合法 那么显然 dp[i][j]=0,否则在判断dp[i][j]能否由dp[i][j-w[i]]+1得到
复杂度O(N*M),而且常数也很小,可以通过楼教主的题目
两种代码如下:
#include <iostream> #include <stdio.h> #include<string.h> #include<algorithm> #include<string> #include<ctype.h> using namespace std; int num[100010]; bool dp[100010]; int a[110]; int c[1010]; int n,m; int main() { freopen("in.txt","r",stdin); //int T,cas=0; //scanf("%d",&T); //while(T--) while(scanf("%d%d",&n,&m),n+m) { //cas++; //scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",a+i); for(int i=1;i<=n;i++) scanf("%d",c+i); memset(dp,0,sizeof(dp)); dp[0]=1; for(int i=1;i<=n;i++) { memset(num,0,sizeof(num)); for(int j=a[i];j<=m;j++) { if(num[j-a[i]]>=c[i]) continue; if(dp[j]||(!dp[j-a[i]])) continue; num[j]=num[j-a[i]]+1; dp[j]=1; } } int ans=0; for(int i=1;i<=m;i++) { ans+=dp[i]; } //printf("Case %d: %d ",cas,ans); printf("%d ",ans); } return 0; }
#include <iostream> #include <stdio.h> #include<string.h> #include<algorithm> #include<string> #include<ctype.h> using namespace std; int dp[100010]; int a[110]; int c[1010]; int n,m; int main() { //freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m),n+m) { for(int i=1;i<=n;i++) scanf("%d",a+i); for(int i=1;i<=n;i++) scanf("%d",c+i); memset(dp,-1,sizeof(dp)); dp[0]=0; int ans=0; for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { if(dp[j]!=-1) { dp[j]=0; } else if(j>=a[i]&&dp[j-a[i]]!=-1&&dp[j-a[i]]<c[i]) { dp[j]=dp[j-a[i]]+1; } } } for(int i=1;i<=m;i++) { ans+=(dp[i]!=-1); } printf("%d ",ans); } return 0; }