1013. 机器分配(分组背包原理,输出方案)

1013. 机器分配(分组背包原理,输出方案)

 原题链接e

分析:

分组背包问题是互斥选择模型,即一个物品组内只能做出一种决策选择,叫做分组背包问题

分组背包问题,如果运用分组背包模型来做的话,如下转换

每个公司看成一个物品组,我们至多可以选择m个,选择0~m个操作是互斥的,只能做一个,

因此对于分给第 i 个 公司 的不同 机器数量 可以分别看作是一个 物品组 内的 物品

状态计算

1013. 机器分配(分组背包原理,输出方案)

初始化:全部初始化为0

状态计算:根据最后一个不同点/最后一次选择来进行划分,可以划分为以下子集

  • 当前选择0个                        dp[i][j]=dp[i-1][j]
  • 当前选择1个                        dp[i][j]=dp[i-1][j-1]
  • ....
  • 当前选择j个                          dp[i][j]=dp[i-1][0]

由于要找出方案具体的选择,但是没有字典序的限制条件,所以可以再遍历一次,记录对于每个公司具体分配了哪些

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1005;
int n,m;
int dp[N][N];
int w[N][N];
int way[N];  //每个公司分配了几个

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>w[i][j];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=j;k++)
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j-k]+w[i][k]);
            }
    cout<<dp[n][m]<<endl;
    int j=m;
    for(int i=n;i;i--)
        for(int k=0;k<=j;k++)   //由于是互斥的,每个公司只能选择一次,找出选择后break
        {
            if(dp[i][j]==dp[i-1][j-k]+w[i][k])
            {
                way[i]=k;
                j-=k;
                break;  //做出选择后break;
            }
        }
    for(int i=1;i<=n;i++)
        cout<<i<<' '<<way[i]<<endl;
    return 0;
}

上一篇:Error (10028): Can't resolve multiple constant drivers for net "**" at **.v


下一篇:【PTA乙级】1013.数素数