【金明的预算方案】 （C++代码）

解题思路:





注意事项:





参考代码:

#include<iostream>using namespace std;
//一维数组不超过 3000 0000
//!!!聪明把最多2件物品的重要度、价格都保存在主件上-这样看每个物品有3个
//v[4][0]-v[4][1]-v[4][2]表示第4件物品的主件价格-第4件物品第1件附件价格
//v-p都变成了二维 [61][3]
int n,m;//n是总的钱--相当于以前的c， 有m件物品---相当于n
int v[61][3];//第i件物品的价格：每个物品最多有2个附件下标全部从1开始
//每件物品的价格,v[i][0]表示主件编号i的价格
//v[i][1]表示主件编号i的附件1的价格
//v[i][2] 示主件编号i的附件2的价格
int p[61][3];//第i件物品中的重要度
//每件物品的重要度,p[i][0]表示主件编号i的重要度
//p[i][1]表示主件编号i的附件1的重要度 p[i][1]
//p[i][2] 表示主件编号i的附件2的重要度 p[i][2]
//f[i][j]=前i件物品总花费为j的选择物品的总和价值最大
/*f[i][j]=max{
f[i-1][j];//1、不背第i件物品
f[i-1][j-v[i][0]]+p[i][0]*v[i][0];     //2、只背主件
f[i-1][j-v[i][0]-v[i][1]]+p[i][0]*v[i][0]+p[i][1]*v[i][1] //3、背主件只要附件1
f[i-1][j-v[i][0]-v[i][2]]+p[i][0]*v[i][0]+p[i][2]*v[i][2]//4、背主件只要附件2

f[i-1][j-v[i][0]-v[i][1]-v[i][2]]+p[i][0]*v[i][0]+p[i][2]*v[i][2] +p[i][1]*v[i][1];//5、背主件加两个附件

} 1000 5

800 2 0

400 5 1

300 5 1

400 3 0

500 2 0

*/

int f[61*3][32000];//f[i][j]前i件物品总钱为j的价值和最大:61*3个附件

void read()
{ int i,j,a,b,c,num=0;//num计主件的个数
int map[61]={0};
cin>>n>>m;//读入总钱数和m件物品
n=n/10;//每件物品都是10的整数倍，可以优化程序
for(i=1;i<=m;i++)
{ cin>>a>>b>>c;//先用变量保存--判断好是主还是附近再赋值
if(c==0) //先填主件，c才是主件
 { num++;//！！计一共有多少个主件，附件都记在主件第二维下标[1][2]
  v[num][0]=a/10;
  p[num][0]=b;//i=4，是第4件其实不是的-因为前面的有可能是附件，而附件不记数
  map[i]=num;//记下第i个物品的主件序号
  continue;
 }
//c是物品的序号是i，不是num，而本题所有的附件要放在num主件上
c=map[c];//i=2,c=1时 c=map[1]=1, i=3时，c=1 ,c=map[1]=1
//i=4,map[4]=2,i=5,map[5]=3
if(v[c][1]==0)//如果第c件物品的第1个附件还没有        { v[c][1]=a/10; p[c][1]=b;         continue;        }     else { v[c][2]=a/10;p[c][2]=b;         }    

}//填好 v,p两个数组

//用背包;--主件和附件最多只被1次-
for(i=1;i<=num;i++)//穷举所有的主件物品:
{
for(j=n;j>=0;j--)    //j是总重量总价格n：！！这是修改j>=0因为j<v[i][0]也要算
{ //情况1：不选主件    :这里把j<v[i][0]的情况也要计算吧
f[i][j]=f[i-1][j];//这时候f[i][j]=f[i-1][j]这个要执行.
//情况2：只选主件
//背得动
if(j>=v[i][0])    //重要度*价格
  f[i][j]=max(f[i][j],f[i-1][j-v[i][0]]+p[i][0]*v[i][0]);
//情况3：选主件和附件1
if(j>=v[i][0]+v[i][1])
 f[i][j]=max(f[i][j],f[i-1][j-v[i][0]-v[i][1]]+p[i][0]*v[i][0]+p[i][1]*v[i][1]);
//情况4：选主件和附件2
if(j>=v[i][0]+v[i][2])
f[i][j]=max(f[i][j],f[i-1][j-v[i][0]-v[i][2]]+p[i][0]*v[i][0]+p[i][2]*v[i][2]);
//情况5：主件+2个附件
if(j>=v[i][0]+v[i][1]+v[i][2])
f[i][j]=max(f[i][j],f[i-1][j-v[i][0]-v[i][1]-v[i][2]]+p[i][0]*v[i][0]+
p[i][1]*v[i][1]+p[i][2]*v[i][2]);  // if(a[i]>x) x=a[i]  x=max(x,a[i]);
} //end for j
}//end for i
cout<<f[num][n]*10;        
}
int main()
{read();
return 0;
}

评论

还没有评论

评论

作者: 浅色调 更新时间: 2017-11-08 21:33  在Ta的博客查看  0 

DP背包问题

思路：分组背包的问题，可以用分组背包来解，但是因为有依赖性(只有选了主件才能选择它的附件)，所以可以转换为有依赖的背包来做(不会的去看背包九讲)。我们设f[i]表示i的钱内能得到的最大价值;g[j]表示在选了某个主件下，j的钱内得到的最大价值(可以理解为将每个主件及其附件也进行01背包的DP)。则不难得到状态转移方程：g[i]=max(g[i],g[i-a[j].price]+a[j].value) (其中j为i的附件)，f[i]=max(f[i],g[i]) (可以这样理解:如果f[i]=f[i],表示不选i主件及其附件,若f[i]=g[i],则表示选了i主件及其附件)

仔细思考，应该很容易理解的。

欢迎来踩博客：five20

评论

还没有评论

评论

作者: ShawnZhou 更新时间: 2017-09-27 13:19  在Ta的博客查看  0 

安利一发自己的博客：http://www.cnblogs.com/OIerShawnZhou/

（我平常写的题解都会往博客里发，欢迎各位大佬前来拍砖）

*上一个题解有一处手误，已更正

带有附件的背包问题，它属于01背包的变式。

这题还好，每一个物品最多只有两个附件，那么我们在对主件进行背包的时候，决策就不再是两个了，而是五个。

还记得01背包的决策是什么吗？

1.不选，然后去考虑下一个

2.选，背包容量减掉那个重量，总值加上那个价值。

这个题的决策是五个，分别是：

1.不选，然后去考虑下一个

2.选且只选这个主件

3.选这个主件，并且选附件1

4.选这个主件，并且选附件2

5.选这个主件，并且选附件1和附件2.

这个。。。很好想吧。。。

我们知道，01背包的状态转移方程（已使用滚动数组优化）是f[j] = max(f[j],f[j-w[i]]+c[i])，那么，这道题的转移方程也就不难写出了。

等等，你得先判断某个选附件的决策是不是可行的，如果当前的容量还够放第一个，或第二个，或两个都选的附件，那么才能考虑转移。

当然，不选附件的话就不用判啦，直接01背包的转移方程即可。

我们令main_item_w数组表示某个主件的费用，而main_item_c数组表示某个主件的价值。

同样的，用二维数组annex_item_w表示某个附件的费用，annex_item_c表示某个附件的价值，第二维只需要0,1,2这三个数，其中第二维是0的场合表示这个主件i的附件数量，它只能等于0或1或2。第二维是1或者是2的值代表以i为主件的附件1或者附件2的相关信息（费用 价值）。这些数组的信息应该在读入时处理好，具体详见代码。

这样，状态转移方程就是四个。

不选附件的①：f[j] = max(f[j],f[j-main_item_w[i]]+main_item_c[i]);

选附件1的②：f[j] = max(f[j],f[ j - main_item_w[i] - annex_item_w[i][1] ] + main_item_c[i] + annex_item_c[i][1]);

选附件2的③：f[j] = max(f[j],f[ j - main_item_w[i] - annex_item_w[i][2] ] + main_item_c[i] + annex_item_c[i][2]);

选附件1和附件2的④：f[j] = max(f[j],f[ j - main_item_w[i] - annex_item_w[i][1] - annex_item_w[i][2] ] + main_item_c[i] + annex_item_c[i][1] + annex_item_c[i][2]);

已经滚动掉了第一维，道理和正常向的01背包都是一样的，即只有i和i-1有关系，但是这个规律在循环中已经满足了所以完全没必要记录。

目标状态f[n]，输出就好。

参考代码：

#include <iostream>#define maxn 32005using namespace std;int n,m;int v,p,q;int main_item_w[maxn];int main_item_c[maxn];int annex_item_w[maxn][3];int annex_item_c[maxn][3];int f[maxn];int main(){    cin >> n >> m;    for (int i=1;i<=m;i++){        cin >> v >> p >> q;        if (!q){
           main_item_w[i] = v;
           main_item_c[i] = v * p;
       }        else{
           annex_item_w[q][0]++;
           annex_item_w[q][annex_item_w[q][0]] = v;
           annex_item_c[q][annex_item_w[q][0]] = v * p;
       }
   }    for (int i=1;i<=m;i++)        for (int j=n;main_item_w[i]!=0 && j>=main_item_w[i];j--){
           f[j] = max(f[j],f[j-main_item_w[i]]+main_item_c[i]);            if (j >= main_item_w[i] + annex_item_w[i][1])
               f[j] = max(f[j],f[ j - main_item_w[i] - annex_item_w[i][1] ] + main_item_c[i] + annex_item_c[i][1]);            if (j >= main_item_w[i] + annex_item_w[i][2])
               f[j] = max(f[j],f[ j - main_item_w[i] - annex_item_w[i][2] ] + main_item_c[i] + annex_item_c[i][2]);            if (j >= main_item_w[i] + annex_item_w[i][1] + annex_item_w[i][2])
               f[j] = max(f[j],f[ j - main_item_w[i] - annex_item_w[i][1] - annex_item_w[i][2] ] + main_item_c[i] + annex_item_c[i][1] + annex_item_c[i][2]);

        }     cout << f[n] << endl;     return 0;
}

评论

还没有评论

评论

作者: Arthur_L 更新时间: 2017-09-26 21:40  在Ta的博客查看  0 

#include <iostream>#include <cstdio>#include <cstring>#include <vector>using namespace std;long long  n,m,tmp=0,v,p,q,x;long long f[65][3205],a[65][3],jz[65][3],o[65];int main(){    cin>>n>>m;
   n=n/10;    for(int i=1;i<=m;i++){        cin>>v>>p>>q;
       v=v/10;        if(q==0){
           tmp+=1;
           a[tmp][0]=v;
           jz[tmp][0]=v*p;
           o[i]=tmp;
       }        else{            if(a[o[q]][1]){
               a[o[q]][2]=v;
               jz[o[q]][2]=v*p;
           }            else{
               a[o[q]][1]=v;
               jz[o[q]][1]=v*p;
           }
       }
   }    for(int i=1;i<=tmp;i++){        for(int j=1;j<=n;j++){            if((j-a[i][0])>=0){
               f[i][j]=max(f[i-1][j],f[i-1][j-a[i][0]]+jz[i][0]);
           }
           else{
               f[i][j]=f[i-1][j];continue;
           }
           if((j-a[i][0]-a[i][1])>=0) f[i][j]=max(f[i][j],f[i-1][j-a[i][0]-a[i][1]]+jz[i][0]+jz[i][1]);            if((j-a[i][0]-a[i][2])>=0) f[i][j]=max(f[i][j],f[i-1][j-a[i][0]-a[i][2]]+jz[i][0]+jz[i][2]);            if((j-a[i][0]-a[i][1]-a[i][2])>=0) f[i][j]=max(f[i][j],f[i-1][j-a[i][0]-a[i][1]-a[i][2]]+jz[i][0]+jz[i][1]+jz[i][2]);
       }
   }    cout<<f[tmp][n]*10;
}

大概就是 分成五种情况 主件附件都不买 只买主件 买主件和附件1 买主件和附件2 买主件和附件1和附件2

还有 存数据要注意！！！！！！（之前没有AC就是存数据的时候GG了）

评论

还没有评论

评论

作者: leylee 更新时间: 2017-09-24 16:30  在Ta的博客查看  0 

思路: 动规题没毛病, 把若干存在附属关系的物品看做是一件物品, 每件物品中有四种组合方式可选, 对每一件物品在每一个剩余钱数进行状态转移时都寻找一遍最优组合... 我太蒻了所以可能没说明白, 看一下代码吧

#include <stdio.h>#include <stdlib.h>struct item {    int cost;    int value;
};struct item goods[62][7];/*
   good[i][0].cost 代表第 i 个附属关系已经有了多少种物品
   good[i][1] ~ good[i][3] 代表每种物品的价格和权值
   good[i][4] ~ good[i][7] 代表四种组合的价格和权值
*/int dp[3202];int i, j, k, l, ma;int n, m;int v, w, q;int main(void){    scanf("%i %i", &n, &m);
   n /= 10;    for (i = 1; i <= m; i++)
   {        scanf("%i %i %i", &v, &w, &q);        if (q)
           k = q;        else
           k = i;

       l = ++goods[k][0].cost;
       goods[k][l].cost = v / 10;    // 价格是 10 的整数倍所以优化常数
       goods[k][l].value = v * w;
   }    for (i = 1; i <= m; i++)
   {        // 体现我蒟蒻属性的代码, 如果没限制最多 2 个附属品我就废了
       goods[i][4].cost = goods[i][1].cost;
       goods[i][4].value = goods[i][1].value;
       goods[i][5].cost = goods[i][1].cost + goods[i][2].cost;
       goods[i][5].value = goods[i][1].value + goods[i][2].value;
       goods[i][6].cost = goods[i][1].cost + goods[i][2].cost;
       goods[i][6].value = goods[i][1].value + goods[i][2].value;
       goods[i][7].cost = goods[i][1].cost + goods[i][2].cost + goods[i][3].cost;
       goods[i][7].value = goods[i][1].value + goods[i][2].value + goods[i][3].value;
   }    for (i = 1; i <= m; i++)        for (k = 0; k <= n; k++)
       {            // 以下和开心的金明不一样
           ma = 0;    // max 的简写
           for (l = 4; l <= 7; l++)    // 对于四种组合的判断
           {                if (k + goods[i][l].cost > n)    // 如果当前组合花费的钱大于剩余钱数就跳过
                   continue;                if (ma < dp[k + goods[i][l].cost] + goods[i][l].value)
                   ma = dp[k + goods[i][l].cost] + goods[i][l].value;    // 更新最大权值
           }            // 以上和开心的金明不一样
           if (dp[k] < ma)
               dp[k] = ma;
       }

   l = 0;    for (i = 0; i <= n; i++)        if (dp[i] > l)
           l = dp[i];    printf("%i\n", l);    return 0;
}