用到至少選擇一個(gè)，所以沒(méi)有空間優(yōu)化
分組背包問(wèn)題：
常見(jiàn)的三種分組問(wèn)題：
分成K組：
1、每組最多只能取一件物品
一維數(shù)組偽碼：
for 0 to K ?對(duì)每一組進(jìn)行
? ? for W to 0 ? 對(duì)每一個(gè)代價(jià)進(jìn)行判斷 ///1
? ? ?for all item i in group k ? ? ? ?///2 這行個(gè)互換好像也對(duì)
? ? ?dp[w]=max(dp[w],dp[w-c[i]]+v[i]; ? 每個(gè)重量保證的只有一件物品來(lái)取最大值
2、每組隨意取（為01背包問(wèn)題）******摘抄網(wǎng)絡(luò)**既然上面的順序是限制每組最多取一個(gè)，那調(diào)換一下順序即可，其實(shí)就是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、每組至少取一個(gè)
沒(méi)見(jiàn)過(guò)一維的偽代碼
用二維：
dp[ki][j]表示當(dāng)前組的一件物品不選
dp[ki-1][j-w[i]]+v[i] 表示這是在ki組選第一個(gè)
dp[ki][j-w[i]]+v[i] 表示在這個(gè)ki組中再次選一個(gè)
dp[ki][j](處理完后的值)=max(dp[ki][j],dp[ki-1][j-w[i]]+v[i],dp[ki][j-w[i]]+v[i]) max分開(kāi)的時(shí)候要注意順序 max(dp[ki][j],dp[ki-1][j-w[i]]+v[i])......
在初始化時(shí)是ki==0（沒(méi)有組）這時(shí)是dp[0][j]=0 其余的是-inf ******解決一件物品都不取的問(wèn)題

?

#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];//當(dāng)前i個(gè)組繼承前i-1個(gè)組}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]);//多個(gè)//dp[i][p]=max(dp[i][p],dp[i-1][p-c[j]]+g[j]);//一個(gè)}}}}// if(dp[n][t]<0)// cout<<-1<<endl;// elsecout<<max(dp[n][t],-1)<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【分组背包问题 (HDU 3535 )】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。