用到至少選擇一個,是以沒有空間優化
分組背包問題:
常見的三種分組問題:
分成K組:
1、每組最多隻能取一件物品
一維數組僞碼:
for 0 to K 對每一組進行
for W to 0 對每一個代價進行判斷 ///1
for all item i in group k ///2 這行個互換好像也對
dp[w]=max(dp[w],dp[w-c[i]]+v[i]; 每個重量保證的隻有一件物品來取最大值
2、每組随意取(為01背包問題)******摘抄網絡**既然上面的順序是限制每組最多取一個,那調換一下順序即可,其實就是01背包。******
一維僞碼:
for 0 t0 K
for all item i in group k
for W to 0
dp[w]=max(dp[w],dp[w-c[i]]+v[i]);
3、每組至少取一個
沒見過一維的僞代碼
用二維:
dp[ki][j]表示目前組的一件物品不選
dp[ki-1][j-w[i]]+v[i] 表示這是在ki組選第一個
dp[ki][j-w[i]]+v[i] 表示在這個ki組中再次選一個
dp[ki][j](處理完後的值)=max(dp[ki][j],dp[ki-1][j-w[i]]+v[i],dp[ki][j-w[i]]+v[i]) max分開的時候要注意順序 max(dp[ki][j],dp[ki-1][j-w[i]]+v[i])......
在初始化時是ki==0(沒有組)這時是dp[0][j]=0 其餘的是-inf ******解決一件物品都不取的問題
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#define X 10005
#define inf 0x3f3f3f3f
using namespace std;
int main()
{
int n,t;
int m,s;
cin>>n>>t;
int dp[105][105];
int c[105],g[105];
memset(dp,-inf,sizeof(dp));
memset(dp[0],0,sizeof(dp[0]));
for(int i=1;i<=n;++i)//k組
{
cin>>m>>s;
for(int j=0;j<m;++j)
{
scanf("%d%d",&c[j],&g[j]);
}
if(s==0)
{
// for(int j=0;j<=t;++j)
// dp[i][j]=-1000000;
for(int j=0;j<m;++j)
for(int p=t;p>=c[j];--p)
{
dp[i][p]=max(dp[i][p],dp[i][p-c[j]]+g[j]);
dp[i][p]=max(dp[i][p],dp[i-1][p-c[j]]+g[j]);
}
}
else if(s==1)
{
for(int j=0;j<=t;++j)
{
dp[i][j]=dp[i-1][j];//目前i個組繼承前i-1個組
}
for(int j=0;j<m;++j)
{
for(int p=t;p>=c[j];--p)
{
dp[i][p]=max(dp[i][p],dp[i-1][p-c[j]]+g[j]);
}
}
}
else if(s==2)
{
for(int j=0;j<=t;++j)
{
dp[i][j]=dp[i-1][j];
}
for(int j=0;j<m;++j)
{
for(int p=t;p>=c[j];--p)
{
// dp[i][p]=max(dp[i][p],dp[i-1][p]);//不取
dp[i][p]=max(dp[i][p],dp[i][p-c[j]]+g[j]);//多個
//dp[i][p]=max(dp[i][p],dp[i-1][p-c[j]]+g[j]);//一個
}
}
}
}
// if(dp[n][t]<0)
// cout<<-1<<endl;
// else
cout<<max(dp[n][t],-1)<<endl;
return 0;
}