分組背包問題

題目描述

核心思路

最大價值應該是物品組i和背包容量j的函數。設

f[i][j]

表示前i組物品，能放入容量為j的背包的最大價值

樸素算法應該是循環物品組，循環背包容量，對第 i i i組物品，容量為 j j j的背包，有 s + 1 s+1 s+1種選法，即 m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v 1 ] + w 1 , f [ i − 1 ] [ j − v 2 ] + w 2 , ⋯   , f [ i − 1 ] [ j − v s ] + w s ) max(f[i-1][j],f[i-1][j-v_1]+w_1,f[i-1][j-v_2]+w_2,\cdots,f[i-1][j-v_s]+w_s) max(f[i−1][j],f[i−1][j−v1​]+w1​,f[i−1][j−v2​]+w2​,⋯,f[i−1][j−vs​]+ws​)

其中 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j]表示我不選擇第 i i i組中的任何一個物品所得到的最大價值， f [ i − 1 ] [ j − v 1 ] + w [ i ] f[i-1][j-v_1]+w[i] f[i−1][j−v1​]+w[i]表示我選擇第 i i i組物品中的第一個物品所得到的最大價值，由于第 i i i組物品中的第一個物品用掉了 v 1 v_1 v1​的體積，那麼還剩下 j − v 1 j-v_1 j−v1​的體積，是以我們從前 i − 1 i-1 i−1組物品中選擇，那麼最大價值就是 f [ i − 1 ] [ j − v 1 ] f[i-1][j-v_1] f[i−1][j−v1​]，然後加上選擇第 i i i組中的第一個物品的價值 w [ i ] w[i] w[i]。是以總的最大價值就是 f [ i − 1 ] [ j − v 1 ] + w [ i ] f[i-1][j-v_1]+w[i] f[i−1][j−v1​]+w[i]

可以對空間進行優化，将 f f f優化為一維

代碼

沒有優化空間， f f f是二維數組

/*
樸素算法：循環物品組,循環背包容量 對于第i組物品,容量為j的背包,有s+1種選法
max(f[i-1][j],f[i-1][j-V1]+W1,f[i-1][j-2V1]+W2,...,f[i-1][j-Vs]+Ws);
*/
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
int v[N][N],w[N][N];    //體積  價值
//f[i][j]表示前i組物品，能放入容量為j的背包的最大價值
int f[N][N];
int s[N];   //s[i]=x表示第i組内有x件物品
int n,m;    //物品  體積

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)   //n組物品
    {
        scanf("%d",&s[i]);  //第i組物品中有s[i]件物品
        for(int j=1;j<=s[i];j++)
            scanf("%d%d",&v[i][j],&w[i][j]);
    }
    for(int i=1;i<=n;i++)   //n組物品
    {
        for(int j=1;j<=m;j++)   //體積
        {
            for(int k=0;k<=s[i];k++)    //決策 選擇該組中的哪個物品
            {
                if(j>=v[i][k])
                {
                    //max中的f[i][j]表示不選第i組中第k個物品，已擷取的價值
                    //f[i-1][j-v[i][k]]+w[i][k]表示選入第i組物品中的第k個物品,能擷取的價值
                    f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
                }
            }
        }
    }
    printf("%d\n",f[n][m]);
    return 0;
}
           

優化空間， f f f是一維數組

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
int v[N],w[N];  //體積  價值
int f[N];   //将物品裝入背包容量為m的最大價值
int n,m;    //體積  價值

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)   //物品
    {
        int s;
        scanf("%d",&s);
        for(int j=1;j<=s;j++)
            scanf("%d%d",&v[j],&w[j]);
        for(int j=m;j>=1;j--)   //體積
        {
            for(int k=0;k<=s;k++)   //決策  選擇第i組中的第k件物品
            {
                if(j>=v[k])
                    f[j]=max(f[j],f[j-v[k]]+w[k]);
            }
        }
    }
    printf("%d\n",f[m]);
    return 0;
}