今日學習了01背包求具體方案的方法

Acwing.12 背包問題求具體方案

由于背包是從小到大枚舉物品，只能從后往前判斷是從哪個狀態遞推過來的，而該題要求按字典序順序輸出字典序最小的最優方案

因此要將物品從大到小枚舉，判斷時從小到大判斷是從哪個狀態遞推過來的即可

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e3+5;
int v[N],w[N];
int f[N][N];int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=n;i++) cin>>v[i]>>w[i];for(int i=n;i;i--)//倒著求才能根據字典序倒推for(int j=1;j<=m;j++){f[i][j]=f[i+1][j];if(j>=v[i]) f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);}int tag=m;for(int i=1;i<=n;i++)if(f[i][tag]==f[i+1][tag-v[i]]+w[i]){//選他的方案if(tag<v[i]) continue;//體積比v[i]小的不能選cout<<i<<' ';tag-=v[i];}return 0;
}

P2066 機器分配

總公司擁有高效設備 M?臺，準備分給下屬的N?個分公司。各分公司若獲得這些設備，可以為國家提供一定的盈利。問：如何分配這M?臺設備才能使國家得到的盈利最大？求出最大盈利值。其中 M≤15，N≤10。分配原則：每個公司有權獲得任意數目的設備，但總臺數不超過設備數 M。

輸入格式

第一行有兩個數，第一個數是分公司數?N，第二個數是設備臺數?M。

接下來是一個?N×M?的矩陣，表明了第?i?個公司分配?j?臺機器的盈利。

輸出格式

第一行為最大盈利值。

接下來?N?行為第?𝑖?分公司分?x?臺。

P.S. 要求答案的字典序最小。

思路

把公司看成分組背包里的每一組，每組選的個數看成體積，存的是最大價值

因此可以把該題看成是分組背包問題

最后更據結果倒退得到路徑輸出即可

90PTS，應該是哪個字典序出現問題了

#include <iostream>
#include <algorithm>
using namespace std;
const int N=16;
int a[N][N],f[N][N];//f[i,j]表示選到第i個公司,設備總數不超過j的盈利最大值
int way[N];int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;//公司數,設備臺數for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=0;k<=j;k++)//選幾臺f[i][j]=max(f[i][j],f[i-1][j-k]+a[i][k]);int k=m;for(int i=n;i;i--)for(int j=0;j<=k;j++)//枚舉上一層是選幾個推過來的if(f[i][k]==f[i-1][k-j]+a[i][j]){way[i]=j;k-=j;break;}cout<<f[n][m]<<'\n';for(int i=1;i<=n;i++)cout<<i<<' '<<way[i]<<'\n';return 0;
}