背包学习————多重背包背包-白红宇

背包学习————多重背包背包

阅读量：5953 次

发布时间：2019-06-19

本文共 1721 字，大约阅读时间需要 5 分钟。

有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]里面选多少个的问题。

实现方法：

1：转化成01背包，将每种背包转换成数量为n[i]的01背包求解

View Code

#include 
      
        #include
       
         #include
        
          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
         
          =c[i];j--)                 {
                        f[j]=max(f[j],f[j-c[i]]+w[i]);                 }             }         }         printf("%d\n",f[n]);     } return 0; }

2：利用二进制的思想（思考中，给出代码实现，原理不理解。。）

View Code

#include 
      
        #include 
       
         #include 
        
          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
         
          n)             cb(c[i],w[i],n); else             {
    int k=1; while(k

3:o(n*v)

View Code

#include 
      
        #include 
       
         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