POJ - 1742-Coins多重背包的可行性问题+二进制拆分优化_综合

Coins
在这个背包模型里面，没有”物品价值“这个属性，不是最优解问题，而是可行性问题。
用多重背包的变形即可。

		bool f[maxn];f[0]=1;for(int i=1;i<=n;i++)for(int j=1;j<=c[i];j++)         for(int k =m;k>=v[i];k--)           f[k] = f[k] | f[k-v[i]];int ans = 0; for(int i=1;i<=n;i++)ans+=f[1];

动态记录过程：
样例：

A[i]: 1 2 4 
C[i]: 2 1 1

0 0 0 0 0 0 0 0 0 0 
1 1 0 0 0 0 0 0 0 0 
1 1 1 1 0 0 0 0 0 0 
1 1 1 1 1 1 1 1 0 0

毫无疑问， $O((\sum_{i=1}^n C_i ) *M)$ 时间复杂度过高，
于是就用最简单的二进制拆分法进行优化。

Solution1
时间复杂度：
$O((\sum_{i=1}^n C_i ) *N*M)$
在这里插入图片描述
擦边过的。
而且很迷惑的是，一旦将boo f[] ,改成int f[]就会TLE,难道整数int 强制转换到bool这么慢？

#include<stdio.h>
#include<iostream>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define ms0(a) memset(a,0,sizeof(a))
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;const int maxn = 105;
const int maxm = 1e5+5;
int n,m,v[maxn],c[maxn];
bool f[maxm];
int main(){while(~scanf("%d%d",&n,&m) && n){ms0(f);ms0(v);ms0(c);for(int i=1;i<=n;i++)scanf("%d",&v[i]);for(int i=1;i<=n;i++)scanf("%d",&c[i]);f[0]=1;for(int i=1;i<=n;i++){int p = (int)log2(c[i]+1)-1;int r = c[i]-pow(2, p+1)+1;int vp[p+5];for(int x=0;x<=p;x++)vp[x]=pow(2, x)*v[i];vp[p+1]=r*v[i];for(int j=0;j<=p+1;j++){for(int k=m;k>=vp[j];k--){f[k] = f[k] | f[k-vp[j]];}}}int ans=0;for(int i=1;i<=m;i++)ans+=f[i];printf("%d\n",ans);}return 0;
}

Solution2
本题是不是一条最优化问题，只是一道可行性问题，
就是说，如果f[j]==true,那么之后便无需更新，
换言之，在选择第i种硬币（第i阶段）的时候，如果f[j]从false到true,只有可能是f[j-v[i]]==true,然后再选择一枚硬币，拼成面值j。
于是借用完全背包的模型，（这样既不用二进制拆分更不用把第二种物品完全拆分），从前往后更新，可以多次加入一个物品，前提是能加（也就是已经加入的次数<c[i]）

核心代码

        for(int i=1;i<=n;i++){ms0(used);for(int j=v[i];j<=m;j++){if(!f[j] && f[j-v[i]] && used[j-v[i]]<c[i]){f[j]=true;used[j]=used[j-v[i]]+1;}}}

AC代码
在这里插入图片描述
时间复杂度：O(n*m)

#include<stdio.h>
#include<iostream>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define ms0(a) memset(a,0,sizeof(a))
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;const int maxn = 105;
const int maxm = 1e5+5;
int n,m,v[maxn],c[maxn],used[maxm];
int f[maxm];
int main(){while(~scanf("%d%d",&n,&m) && n){ms0(v);ms0(c);ms0(f);for(int i=1;i<=n;i++)scanf("%d",&v[i]);for(int i=1;i<=n;i++)scanf("%d",&c[i]);f[0]=true;for(int i=1;i<=n;i++){ms0(used);for(int j=v[i];j<=m;j++){if(!f[j] && f[j-v[i]] && used[j-v[i]]<c[i]){f[j]=true;used[j]=used[j-v[i]]+1;}}}int ans=0;for(int i=1;i<=m;i++)ans+=f[i];printf("%d\n",ans);}return 0;
}