POJ 1742 Coins（多重背包变型，楼教主男人八题）

Description

Input

Output

Sample Input

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

Sample Output

8
4

Source

思路：

一开始的想法就是按照完全背包做，然后将可能会出现的数用一个bool数组储存起来，然后最后遍历有多少种数但是TLE了，方法笨了点。第二种的思路就是把背包容量遍历1到m，统计所有F[i]==i的情况，但是也是超时了。妈个鸡的...果真是男人八题之一...想了一天了都...第三种思路，就是还是多重背包放东西，然后这次不把F[j]给算出来了，而是看一看这个F[j]有没有出现过就好了。一开始的想法还是想用方法一那样的方法储存遍历去做，但还是会大大增加时间复杂度，所以我就试了试直接用bool型来表示F[j].大体想法是这样的：就比如举个样例的例子吧，现在拥有的钱分别是1，1，2，4.那么我从第一个开始，1出现了，那么F[1]=1，然后1+1，F[2]=1，1+4，F[5]=1，然后F[6]F[7]F[8]。这是顺着推出来的顺序，那么现在反过来看，如果F[8]出现了，那么就看F[8]本身是不是已经被标记成1了，如果它本身已经出现过，那么他还是被标记着，然后这时候用8分别去减1减2减4，就会出现F[7]F[6]F[4]，试想，如果F[8]可以通过减去某个拥有的值得到一个被标记的值，那么被标记的值加上这个被减的数一定可以得到这个8，所以说，如果F[8]可以通过减去某个拥有的值得到一个被标记的值，那么这个值也会被标记。实际上这里就是这个多重背包的变型之处。大体的框架还是依靠多重背包来完成，只需要对01背包和完全背包的处理部分进行改写即可。

代码：

//1WA代码   做法是想用标记的方法找出F[i]的所有可能值
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
 
int Max(int a,int b){ return a>b?a:b; }     
int c[101], n1[101];//c:费用 w:价值 n1:数量    
int f[100001];//f[与V有关],c和w[与n]有关 
bool dp[1000001];   
int v, V, V1;//V:容量 V1:容量2    
   
int main()
{
	//freopen("in.txt","r",stdin);
	int n, m;//n:物品种数    
    int i, j;    
    while(scanf("%d%d", &n, &m)!=EOF&&n&&m)
	{
		memset(dp,0,sizeof(dp));
		long long sum=0;
		for (i = 1; i <= n; i++)    
	    {    
	        scanf("%d", &c[i]);    
	    } 
		for (i = 1; i <= n; i++)    
	    {    
	        scanf("%d", &n1[i]);    
	    }       
	    for(i=1;i<=n;i++)
	    {
	    	sum=sum+c[i]*n1[i];
	    }
	    memset(f, 0, sizeof(f));    
	    for (i = 1; i <= n; i++)    
	    {    
		    if (c[i] * n1[i] >= m)    
		    {    
			    for (int v = c[i]; v <= m; v++)    
			    {    
			        f[v] = Max(f[v], f[v-c[i]] + c[i]);
					dp[f[v]]=1;    
			    }       
		    }    
		    else    
		    {    
		        int k = 1;    
		        while (k < n1[i])    
		        {     
					for (int v = m; v >=k*c[i]; v--)    
				    {    
				        f[v] = Max(f[v], f[v-k*c[i]] + k*c[i]); 
						dp[f[v]]=1;   
				    }       
		            n1[i] -= k;    
		            k <<= 1;    
		        }    
				for (int v = m; v >=k*c[i]; v--)    
			    {    
			        f[v] = Max(f[v], f[v-n1[i]*c[i]] + n1[i]*c[i]); 
					dp[f[v]]=1;   
			    }     
		    }       
	    }   
		int ans=0; 
	    for(int t=1;t<=sum;t++)
	    {
	    	if(dp[t]==1)ans++;
	    }
	    printf("%d\n", ans);   
	}    
} 

//2WA代码  做法是背包容量遍历1到m，统计所有F[i]==i的情况
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
  
int a[101], c[101];   
int F[100001];//F[与V有关]

int max(int a,int b)
{
	return a>b?a:b;
}  

void ZeroOnePack(int cost, int weight, int V) 
{ 
    for (int v=V; v>=cost; --v) 
        F[v] = max(F[v], F[v-cost]+weight); 
} 

void CompletePack(int cost, int weight, int V) 
{ 
    for (int v=cost; v<=V; ++v) 
        F[v] = max(F[v], F[v-cost]+weight); 
} 

void MultiPack(int cost, int weight, int V, int amount) 
{ 
    if (cost*amount>=V) { 
        CompletePack(cost, weight, V); 
        return; 
    } 
    int k = 1; 
    while (k<amount) { 
        ZeroOnePack(cost*k, weight*k, V); 
        amount -= k; 
        k *= 2; 
    } 
    ZeroOnePack(cost*amount, weight*amount, V); 
} 

   
int main()
{
	freopen("in.txt","r",stdin);
	int n, m;//n:物品种数      
    while(scanf("%d%d", &n, &m)!=EOF&&n&&m)
	{
	    for (int i=1; i<=n; ++i) 
            scanf("%d",&a[i]); 
        for (int i=1; i<=n; ++i) 
            scanf("%d",&c[i]); 
        int ans=0;
        for (int V=1; V<=m; ++V) 
		{ 
            F[0] = 0; 
            memset(F,0,sizeof(F));
            for (int i=1; i<=n; ++i) 
                MultiPack(a[i], a[i], V, c[i]); 
            if (F[V]==V) 
                ++ans; 
        } 
        printf("%d\n",ans);
	}  
	return 0;  
} 

//3A代码 终于过了...
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
  
int a[101], c[101];   
bool F[100001];//F表示钱的种数 

int max(int a,int b)
{
	return a>b?a:b;
}  

void ZeroOnePack(int cost, int weight, int V) 
{ 
    for (int v=V; v>=cost; --v) //用容量去买东西 
    {
    	if(F[v]==1||F[v-cost]==1)F[v]=1;//如果我买这个东西或者不买这个东西的价钱都出现过，则它也可以出现 
    	else F[v]=0;
    }
} 

void CompletePack(int cost, int weight, int V) 
{ 
    for (int v=cost; v<=V; ++v) 
    {
    	if(F[v]==1||F[v-cost]==1)F[v]=1;
    	else F[v]=0;
    }
} 

void MultiPack(int cost, int weight, int V, int amount) 
{ 
    if (cost*amount>=V) { 
        CompletePack(cost, weight, V); 
        return; 
    } 
    int k = 1; 
    while (k<amount) { 
        ZeroOnePack(cost*k, weight*k, V); 
        amount -= k; 
        k *= 2; 
    } 
    ZeroOnePack(cost*amount, weight*amount, V); 
} 

   
int main()
{
	//freopen("in.txt","r",stdin);
	int n, m;//n:物品种数      
    while(scanf("%d%d", &n, &m)!=EOF&&n&&m)
	{
	    for (int i=1; i<=n; ++i) 
            scanf("%d",&a[i]); 
        for (int i=1; i<=n; ++i) 
            scanf("%d",&c[i]); 
        int ans=0;
        memset(F,0,sizeof(F));
        F[0]=1;
        for (int i=1; i<=n; ++i) 
            MultiPack(a[i], a[i], m, c[i]); 
        for(int i=1;i<=m;++i) 
            ans+=F[i]; 
        printf("%d\n",ans);
	}  
	return 0;  
}