首页 > 代码库 > HDU2159 二重完全背包

HDU2159 二重完全背包

2024-07-23 11:18:49   216人阅读

和普通的完全背包不同的地方时多了物品选取的限制，因此需要增加一维

dp[i][j][k]表示前i种物品，选取j个放入容量为k的背包中所能得到的最大价值

这里和一维的背包一样可以利用滚动数组省略一维即

dp[i][j] 表示前选取i个放入容量为j的背包所能得到的最大价值

dp[i,j] = max(dp[i,j],dp[i-1][j-w[k]]+v[k]);

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <string> 4 #include <algorithm> 5 #include <iostream> 6 using namespace std; 7 #define INF 0x3fffffff 8 const int maxn = 105; 9 const int maxv = 105;10 int dp[maxv][maxn],w[maxn],v[maxn];11 int main()12 {13    //freopen("in.txt","r",stdin);14     int n,m,k,s;15     while(cin>>n>>m>>k>>s)16     {17         for(int i = 1;i<=k;++i)18             scanf("%d%d",v+i,w+i);19         memset(dp,0,sizeof(dp));20         int flag = 0,ans = -1;21         for(int j = 0;j<=m;++j)22         {23             for(int i = 1;i<=s;++i)24             {25                 for(int x = 1;x<=k;++x)26                     if(j>=w[x]){27                             dp[i][j] = max(dp[i][j],dp[i-1][j-w[x]]+v[x]);28                             if(dp[i][j]>=n){flag = 1;ans = j;break;}29                     }30                 if(flag)break;31             }32             if(flag)break;33         }34         if(flag)printf("%d\n",m-ans);35         else puts("-1");36     }37     return 0;38 }

 

HDU2159 二重完全背包


联系
我们