HDU 2191多重背包问题、

时间：2022-12-12 21:39:53
 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 const int qq=+;

 int v[qq],w[qq],dp[qq];

 using namespace std;

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--){

         int n,m;

         scanf("%d %d",&n,&m);

         memset(dp,,sizeof(dp));

         memset(v,,sizeof(v));

         memset(w,,sizeof(w));

         int count=;

         for(int i=;i<m;++i){

             int value,weight,tot;

             scanf("%d %d %d",&value,&weight,&tot);

             int t=;

             while(tot>=t){

                 v[count]=t*value;

                 w[count++]=t*weight;

                 tot-=t;

                 t<<=;

             }

             if(tot){

                 v[count]=tot*value;

                 w[count++]=tot*weight;

             }

         }

         for(int i=;i<count;++i)

             for(int j=n;j>=v[i];--j)        //j必须从n开始dp，如果循序开始dp的话v[i]会被取多次

                 dp[j]=max(dp[j],dp[j-v[i]]+w[i]);     //也就是说达不到01背包要求的v[i]只有取和不取两种状态、

             printf("%d\n",dp[n]);

     }

 }

算法时间复杂度O(V*∑log n[i])

总算是理解了为什么要逆序dp

#include <stdio.h>

.#include <string.h>

.#include <algorithm>

.using namespace std;

.int main()

.{

.    int ncase,p[],w[],c[],dp[];

.    scanf("%d",&ncase);

.    while(ncase--)

.    {

.        int n,m,count=;

.        scanf("%d %d",&n,&m);

.        for(int i=;i<m;i++)

.        scanf("%d %d %d",&p[i],&w[i],&c[i]);

.        memset(dp,,sizeof(dp));

.        int temp=;

.        for(int i=;i<m;i++)

.        {

.            for(int j=n;j>=p[i];j--)//唉在这里又错了几次 要倒着来。

.            {

.                for(int k=;k<=c[i];k++)

.                {

.                    if(j<k*p[i]) break;

.                    dp[j]=max(dp[j-k*p[i]]+k*w[i],dp[j]);

.                    if(dp[j]>temp)

.                    temp=dp[j];

.                }

.            }

.        }

.        printf("%d\n",temp);

.    }

.    return ;

.}

上述代码是借鉴别人的、   也是多重背包最原始的解法

时间复杂度O(V*∑n[i])

相关文章