题目描述:
主件 | 附件 |
电脑 | 打印机,扫描仪 |
书柜 | 图书 |
书桌 | 台灯,文具 |
工作椅 | 无 |
输入:
输入的第 1 行,为两个正整数,用一个空格隔开:N m
输出:
输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值( <200000 )
样例:
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
输出:
2200
分析:这个就是01背包问题,但是有一个附加条件是附件只有在其主件已经购买的情况下才能购买。
首先先把01背包解释清楚,以前也看过,一直不是很明白,今天搞了一天终于基本理解。
假设有一个背包,可以装重量为W,现在有m件物品,每件物品价值为vi,重量为wi,怎样装能使背包价值最大?
01背包隐含条件是每个物品只有一件,状态只有放或者不放。
定义一个数组c[][],c[i][w]前i件物品放到一个容量为w的背包中可以获得最大价值。那么对于每件物品i,可以分为放或者不放,具体:
(1)如果wi>w,那么不能放入背包,c[i][w]=c[i-1][w];
(2)如果wi<=w,那么可以选择放或者不放,分别对于转移方程:c[i][w]=c[i-1][w-wi]+v[i],c[i][w]=c[i-1][w];取两者中较大值,即
c[i][w]=max{c[i-1][w-wi]+v[i],c[i-1][w]}
好啦,01背包理解了这个题就好办了,两个地方需要改动:
1. 价值是vi*di(di是第i个物品的度)
2. 物品i若是附件,需要判断其主件是否已经加入背包。这里可以用一个矩阵flag[][]记录每个状态下每个物品是否加入背包。如果附件要加入背包,先判断主件是否在w-wi的背包里,嗯,这里要注意一下。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <stdlib.h>
#define MAX_N 32000
#define MAX_M 60
using namespace std;
int Knapsack(int v[],int w[],int pro[],int N,int m)
{
int c[MAX_M][MAX_N],i,j;
bool flag[MAX_M][MAX_N];
memset(c,0,sizeof(c));
memset(flag,false,sizeof(flag));
for(i=1;i<=m;i++)
{
for(j=0;j<=N;j++)
{
if(pro[i]==0)
{
c[i][j]=c[i-1][j];
if(v[i]<=j&&c[i][j]<c[i-1][j-v[i]]+v[i]*w[i])
{
c[i][j]=c[i-1][j-v[i]]+v[i]*w[i];
flag[i][j]=true;
}
}
else
{
c[i][j]=c[i-1][j];
if(v[i]<=j&&c[i][j]<c[i-1][j-v[i]]+v[i]*w[i])
{
if(flag[pro[i]][j-v[i]])
c[i][j]=c[i-1][j-v[i]]+v[i]*w[i];
}
}
}
}
return c[m][N];
}
int main()
{
freopen("in.txt","r",stdin);
int v[MAX_M],w[MAX_M],pro[MAX_M],N,m;
scanf("%d%d",&N,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&v[i],&w[i],&pro[i]);
}
printf("%d\n",Knapsack(v,w,pro,N,m));
return 0;
}