背包學習————多重背包背包

有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

狀态轉移方程：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

此時他面臨的不是01背包的選與不選的問題，而是從n[i]裡面選多少個的問題。

實作方法：

http://acm.hdu.edu.cn/showproblem.php?pid=2191

1：轉化成01背包，将每種背包轉換成數量為n[i]的01背包求解

View Code

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N  107
#define inf 9999999
int c[N],w[N],f[N],b[N];
int max(int x,int y)
{
return x>y? x:y;
}
int main()
{
int t,i,j,n,m,k;
    scanf("%d",&t);
while(t--)
    {
        memset(f,0,sizeof(f));
        scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
        scanf("%d%d%d",&c[i],&w[i],&b[i]);
for(i=0;i<m;i++)
        {
for(k=0;k<b[i];k++)
            {
for(j=n;j>=c[i];j--)
                {
                    f[j]=max(f[j],f[j-c[i]]+w[i]);
                }
            }
        }
        printf("%d\n",f[n]);
    }
return 0;
}      

2：利用二進制的思想（思考中，給出代碼實作，原理不了解。。）

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int max_s = 1007;
int c[max_s],w[max_s],b[max_s],f[max_s];
void zb(int c,int w,int n)
{
for(int i=n;i>=c;i--)
    f[i]=max(f[i],f[i-c]+w);
}
void cb(int c,int w,int n)
{
for(int i=c;i<=n;i++)
    {
        f[i]=max(f[i],f[i-c]+w);
    }
}
int main()
{
int t,i,n,m;
    scanf("%d",&t);
while(t--)
    {
        scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
        scanf("%d%d%d",&c[i],&w[i],&b[i]);
        memset(f,0,sizeof(f));
for(i=0;i<m;i++)
        {
if(c[i]*b[i]>n)
            cb(c[i],w[i],n);
else
            {
int k=1;
while(k<b[i])
                {
                    zb(k*c[i],k*w[i],n);
                    b[i]-=k;
                    k*=2;
                }
                zb(b[i]*c[i],b[i]*w[i],n);
            }
        }
        printf("%d\n",f[n]);
    }
return 0;
}      

#include <cstdio>
#include <iostream>
using namespace std;
const int max_s = 107;
int f[100007],w[max_s],b[max_s];
//f[i]來表示目前i價格是否出現過，
int sum[100007];//當價格達到i時，最多使用這一種硬币的次數
int main()
{
int n,V,i,j;
while(scanf("%d%d",&n,&V),n+V)
    {
int ans=0;
for(i=0;i<n;i++)
        scanf("%d",&w[i]);
for(i=0;i<n;i++)
        scanf("%d",&b[i]);
for(i=f[0]=1;i<=V;i++) f[i]=0;
for(i=0;i<n;i++)
        {
for(j=0;j<=V;j++) sum[j]=0;//關鍵是用sum來限定了次數
            for(j=w[i];j<=V;j++)//從w[i]到V循環檢檢視是否能夠出現前邊沒有出現的價格
            {
if(!f[j]&&f[j-w[i]]&&sum[j-w[i]]<b[i])
//如果j價格沒有出現過，且j-w[i]出現過，并且使用i硬币的次數沒有超出給定的數量
                {
                    f[j]=1;//标記為已出現過
                    sum[j]=sum[j-w[i]]+1;//使用次數+1
                    ans++;//滿足條件++
                }
            }
        }
        cout<<ans<<endl;
    }
}