题目描述如下
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 NNN 元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件 附件
电脑 打印机，扫描仪
书柜 图书
书桌 台灯，文具
工作椅 无
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 000 个、 111 个或 222 个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 NNN 元。于是，他把每件物品规定了一个重要度，分为 555 等：用整数 1−51-51−5 表示，第 555 等最重要。他还从因特网上查到了每件物品的价格（都是 101010 元的整数倍）。他希望在不超过 NNN 元（可以等于 NNN 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第 jjj 件物品的价格为 v[j]v_[j]v[j] ，重要度为 w[j]w_[j]w[j] ，共选中了 kkk 件物品，编号依次为 j1,j2,…,jkj_1,j_2,…,j_kj1,j2,…,jk ，则所求的总和为：
v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk]v_[j_1] \times w_[j_1]+v_[j_2] \times w_[j_2]+ …+v_[j_k] \times w_[j_k]v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk] 。
请你帮助金明设计一个满足要求的购物单。
思路
那么普通的01背包下，状态转移方程（采用滚动数组优化）为
f[j]=max(f[j],f[j-c[i]]+w[i]);//w为价值，c为价格
本题加入了附件系统，即在选择时，有四种方案
1、只选主件
2、主件+附件①
3、主件+附件②
4、主件＋附件①+附件②
分别对应的状态转移方程可以根据普通01背包推出，分别是
f[j]=max(f[j],f[j-c[i]]+w[i]);//w为价值，c为价格
f[j]=max(f[j],f[j-c[i]-d[i][]]+w[i]+m[i][]);//w为价值，c为价格,d为附件的价格
f[j]=max(f[j],f[j-c[i]-d[i][]]+w[i]+m[i][]);//w为价值，c为价格,d为附件的价格
f[j]=max(f[j],f[j-c[i]-d[i][]-d[i][]]++m[i][]+w[i]+m[i][]);//w为价值，c为价格,d为附件的价格
状态转移方程不难推出，对应的代码实现也就很简单，两重循环就可以搞定。要注意的就是合理储存数据，在写代码的时候保持思路清晰，不要被多个变量搞混
上代码
/*
有四种取件的模式
1、只买主件
2、主件+附件1
3、主件+附件2
4、主件+附件1+附件2
*/ #include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std; int n,m;
const int maxn=;
int f[maxn];
int item[][];
int c[][];
void init()
{
cin>>n>>m;
memset(item,,sizeof(item));
memset(c,,sizeof(c));
/*
for(int i=1;i<=1000;i++)
for(int j=1;j<=3;j++)
item[i][j]=0;*/
for(int i=;i<=m;i++)
{
int aa,bb,cc;
cin>>aa>>bb>>cc;
// cout<<aa<<' '<<bb<<' '<<cc;
// cout<<endl;
if(cc==)
{ item[i][]=aa*bb;//item[i][1]保存主件的价值,sum保存主件的数量
c[i][]=aa;//c保存主件的花费
}
else
{
item[cc][]++;//item[i][0]保存主件有几件附件
// cout<<cc<<' '<<item[cc][0]+1;
item[cc][item[cc][]+]=aa*bb;//item[i][n]保存附件的价值
// cout<<' '<<item[cc][item[cc][0]+1];
c[cc][item[cc][]+]=aa;//c[i][n]保存附件的花费
// cout<<' '<<c[cc][item[cc][0]+1];//c[i][n]保存附件的花费
}
//cout<<'*'<<item[1][3]<<'*'<<i<<'*'<<endl;
//cout<<endl; }
/*
for(int i=1;i<=m;i++)
{
for(int j=1;j<=3;j++) cout<<item[i][j]<<' ';
cout<<endl;
}
*/
/*
for(int i=1;i<=m;i++)
{
for(int j=1;j<=3;j++)
cout<<c[i][j]<<' ';
cout<<endl;
}
*/
} void slove()
{ for(int i=;i<=m;i++)
{
if(item[i][]!=)
for(int j=n;j>=c[i][];j--)
{
/// cout<<'*'<<max(f[j],f[j-c[i][1]]+item[i][1])<<endl;
if(f[j]<max(f[j],f[j-c[i][1]]+item[i][1]))
{
f[j]=max(f[j],f[j-c[i][]]+item[i][]);
} //cout<<"**"<<max(f[j],f[j-c[i][1]-c[i][2]]+item[i][1]+item[i][2])<<endl; if(j>=c[i][]+c[i][]&&f[j]<max(f[j],f[j-c[i][]-c[i][]]+item[i][]+item[i][]))
f[j]=max(f[j],f[j-c[i][]-c[i][]]+item[i][]+item[i][]); // cout<<"***"<<max(f[j],f[j-c[i][1]-c[i][3]]+item[i][1]+item[i][3])<<endl; if(j>=c[i][]+c[i][]&&f[j]<max(f[j],f[j-c[i][]-c[i][]]+item[i][]+item[i][]))
f[j]=max(f[j],f[j-c[i][]-c[i][]]+item[i][]+item[i][]); // cout<<"****"<<max(f[j],f[j-c[i][1]-c[i][2]-c[i][3]]+item[i][3]+item[i][1]+item[i][2])<<endl; if(j>=c[i][]+c[i][]+c[i][]&&f[j]<max(f[j],f[j-c[i][]-c[i][]-c[i][]]+item[i][]+item[i][]+item[i][]))
f[j]=max(f[j],f[j-c[i][]-c[i][]-c[i][]]+item[i][]+item[i][]+item[i][]);
}
}
cout<<f[n]<<endl;
} int main()
{
// freopen("budget.in","r",stdin);
// freopen("budget.out","w",stdout);
init();
slove();
return ;
}
一点注意
昨晚在洛谷上评测反复re，经过神犇cy的指教，我的代码错在访问数组时未能保证下标合法
if(j>=c[i][]+c[i][]+c[i][]&&f[j]<max(f[j],f[j-c[i][]-c[i][]-c[i][]]+item[i][]+item[i][]+item[i][])) //正确的写法
if(f[j]<max(f[j],f[j-c[i][]-c[i][]-c[i][]]+item[i][]+item[i][]+item[i][])&&j>=c[i][]+c[i][]+c[i][]) //错误的写法
第二种写法中先访问了[j-c[i][1]-c[i][2]-c[i][3]]，而我们没有预先判断它是否大于0，所以会造成re，以后一定要注意；
其次就是要看清题，输入数据的最后一个数字是对应的第几行的附件，而不是第几个主件的附件，这一点没有注意到导致到今天上午才AC
继续切题。。