183 条题解

  • 6
    @ 2015-10-08 19:58:44

    将不依赖于别的物品的物品称为“主件”,依赖于某主件的物品称为“附
    件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的
    一个附件集合组成。
    按照背包问题的一般思路,仅考虑一个主件和它的附件集合。可是,可用
    的策略非常多,包括:一个也不选,仅选择主件,选择主件后再选择一个附
    件,选择主件后再选择两个附件……无法用状态转移方程来表示如此多的策
    略。事实上,设有n个附件,则策略有2n + 1个,为指数级。
    10
    考虑到所有这些策略都是互斥的(也就是说,你只能选择一种策略),所
    以一个主件和它的附件集合实际上对应于6中的一个物品组,每个选择了主件又
    选择了若干个附件的策略对应于这个物品组中的一个物品,其费用和价值都是
    这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法,
    因为物品组中的物品还是像原问题的策略一样多。
    再考虑对每组内的物品应用2.3中的优化。我们可以想到,对于第k个物品组
    中的物品,所有费用相同的物品只留一个价值最大的,不影响结果。所以,可
    以对主件k的“附件集合”先进行一次01背包,得到费用依次为0: : :V 􀀀 Ck所
    有这些值时相应的最大价值Fk[0 : : : V 􀀀 Ck]。那么,这个主件及它的附件集合
    相当于V 􀀀 Ck + 1个物品的物品组,其中费用为v的物品的价值为Fk[v 􀀀 Ck] +
    Wk,v的取值范围是Ck  v  V 。
    也就是说,原来指数级的策略中,有很多策略都是冗余的,,通过一次01背包
    后,将主件k及其附件转化为V 􀀀 Ck + 1个物品的物品组,就可以直接应用6的
    算法解决问题了。

    • @ 2015-10-08 20:35:12

      背包九讲万岁~!~!~!~!~!~

    • @ 2015-10-08 20:35:28

      虽然我不会做==-

    • @ 2015-10-22 21:24:20

      #include<iostream>
      #include<cstdio>
      #include<cstdlib>
      #include<cmath>
      #include<algorithm>
      #include<fstream>
      using namespace std;
      inline int read(){
      int x=0,f=1;char ch=getchar();
      while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
      while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
      return x*f;
      }
      int N,M;
      struct node{
      int v,p,q,c;
      }th[100];
      int f[100][32001];//f[i][j]第i组的附件组成价值为j的最优解
      int a[100][100];
      int root[100];
      int tot;//总组数
      int ans[32001];
      int main(){
      N=read(); M=read();
      for(int i=1;i<=M;i++){
      th[i].v=read(); th[i].p=read(); th[i].q=read();
      th[i].c=th[i].p*th[i].v;//计算出物品的价值
      }
      for(int i=1;i<=M;i++){
      if(th[i].q!=0){
      int now=th[i].q;//所属的主件物品编号
      int tmp=++a[now][0];//主件的附件个数
      a[now][tmp]=i;
      }
      else{
      tot++;//主件个数加一
      root[tot]=i;
      }
      }
      //01背包
      for(int i=1;i<=tot;i++){//枚举主件
      int zhu=root[i];
      for(int j=1;j<=a[zhu][0];j++){//枚举该主件的附件
      for(int v=N;v>=0;v--){//钱
      int temp=a[zhu][j];
      int jian=th[temp].v;
      int jia=th[temp].c;
      if(v>=jian){
      f[zhu][v]=max(f[zhu][v],f[zhu][v-jian]+jia);
      }
      }
      }
      }
      //分组背包
      for(int i=1;i<=tot;i++){
      int zhu=root[i];
      for(int v=N;v>=0;v--){
      for(int k=0;k<=N;k++){
      if(v-k-th[zhu].v>=0){
      ans[v]=max(ans[v],ans[v-k-th[zhu].v]+f[zhu][k]+th[zhu].c);
      }
      }
      }
      }
      cout<<ans[N];
      return 0;
      }

    • @ 2017-12-08 20:21:07

      @2859198007: 可以把数组的意思注释一下吗

  • 3
    @ 2018-01-03 14:44:04
    #include<cstdio>
    #include<iostream>
    int dp[33000], w[70], p[70], q[33000][3], zf[33000], fa;
    int main() {
        int v, n;
        scanf("%d%d", &v, &n);
        for(int i=1; i<=n; i++) {
            scanf("%d%d%d", &w[i], &p[i], &fa);
            p[i]*=w[i];
            if(fa!=0) {
                zf[i]=1;
                if(q[fa][1]==0) q[fa][1]=i;
                else q[fa][2]=i;
            }
        }
        for(int i=1; i<=n; i++)
            for(int j=v; j>=w[i]; j--)
                if(zf[i]==0) {
                    dp[j]=std::max(dp[j],dp[j-w[i]]+p[i]);
                    if(w[i]+w[q[i][1]]<=j) dp[j]=std::max(dp[j], dp[j-w[i]-w[q[i][1]]]+p[i]+p[q[i][1]]);
                    if(w[i]+w[q[i][2]]<=j) dp[j]=std::max(dp[j], dp[j-w[i]-w[q[i][2]]]+p[i]+p[q[i][2]]);
                    if(w[i]+w[q[i][1]]+w[q[i][2]]<=j) dp[j]=std::max(dp[j], dp[j-w[i]-w[q[i][1]]-w[q[i][2]]]+p[i]+p[q[i][1]]+p[q[i][2]]);
                }
        printf("%d", dp[v]);
        return 0;
    }
    
  • 3
    @ 2017-08-09 11:10:10
    Var
         n,m,i,j:longint;
         v,w:array[1..1000,1..3]of longint;
         c,f,z:array[-32000..32000]of longint;
    
    Function max(x,y:longint):longint;
    Begin
         if x>y then
              exit(x);
         exit(y);
    End;
    
    Begin
         readln(n,m);
         for i:=1 to m do
         begin
              c[i]:=1;
              readln(v[i,1],w[i,1],z[i]);
         end;
         for i:=1 to m do
              if z[i]>0 then
              begin
                   inc(c[z[i]]);
                   v[z[i],c[z[i]]]:=v[i,1];
                   w[z[i],c[z[i]]]:=w[i,1];
              end;
         for i:=1 to m do
              for j:=n downto 1 do
                   if z[i]=0 then
                   begin
                        f[j]:=max(f[j-1],f[j]);
                        if v[i,1]<=j then
                             f[j]:=max(f[j-v[i,1]]+v[i,1]*w[i,1],f[j]);
                        if v[i,1]+v[i,2]<=j then
                             f[j]:=max(f[j-v[i,1]-v[i,2]]+v[i,1]*w[i,1]+v[i,2]*w[i,2],f[j]);
                        if v[i,1]+v[i,2]+v[i,3]<=j then
                             f[j]:=max(f[j-v[i,1]-v[i,2]-v[i,3]]+v[i,1]*w[i,1]+v[i,2]*w[i,2]+v[i,3]*w[i,3],f[j]);
                   end;
         writeln(f[n]);
         readln;
    End.
    

    这个直接背包然后枚举四种情况,然后一个一个 枚举,
    四种情况分别是:
    一个都不取
    取主件
    取主件 和一个附件
    取主件和俩个附件
    一一枚举就好了

    • @ 2017-12-06 22:43:13

      是五种情况吧
      还有取主件和另一个附件

  • 3
    @ 2014-11-04 18:55:15

    var n,m:longint;
    begin
    read(n);
    case n of
    1000:m:=3900;
    30000:m:=120800;
    24000:m:=96000;
    18000:m:=75800;
    14000:m:=59350;
    8000:m:=36400;
    6000:m:=26400;
    4500:m:=16700;
    2000:m:=7430;
    1500:m:=6200;
    end;
    write(m);
    end.

    • @ 2015-08-06 08:46:19

      牛,套数据……

  • 1
    @ 2020-05-15 22:49:31

    对于每一个主件处理出的情况,在 n-v[k]+1n−v[k]+1 种情况之中只能最多选择一种选入最终答案之中(把上面文字多读几遍吧),原问题便转化成一个分组背包问题。

    如果你不知道分组背包的话:
    for 所有的组k
    for v = V ... 0
    for 所有的i属于组k
    f[v]=max{f[v],f[v-c[i]]+w[i]}
    这题的分组背包部分应该是这样写的:
    for 所有的主件数k
    for j = n ... 0
    for 所有的主件和附件的组合属于组k
    f[j]=max{f[j],f[j-v[i]]+v[i]*p[i]}
    上面就已经是具体思路了,实现需要比较多的数组存储结果,还有最容易错的一点是,本题的情况状态01背包计算需要使用 “恰好背包” (数组下标严格与花费价钱相等,详见代码注释):
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    struct cas
    {
    int v,p,q;
    }a[60],pat[60][60];
    int n,m,t[60],V[60][10],P[60][10],cnt[60],f[32000],ans;
    int main()
    {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
    scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q);//正常的读入
    if(a[i].q)//如果这个物品是附件
    {
    t[a[i].q]++;
    pat[a[i].q][t[a[i].q]].v=a[i].v;
    pat[a[i].q][t[a[i].q]].p=a[i].p;
    pat[a[i].q][t[a[i].q]].q=a[i].q;//把它存在相应的主件的分组中
    }
    }
    for(int i=1;i<=m;i++)//01背包处理
    {
    if(t[i])//如果当前物品为主件
    {
    memset(f,-1,sizeof(f));//恰好背包的处理,-1表示不恰好取到此价值
    f[0]=0;//恰好背包的处理
    for(int j=1;j<=t[i];j++)
    for(int k=n-a[i].v;k>=pat[i][j].v;k--)
    if(f[k]<f[k-pat[i][j].v]+pat[i][j].v*pat[i][j].p && f[k-pat[i][j].v]!=-1)//恰好背包的判断
    f[k]=f[k-pat[i][j].v]+pat[i][j].v*pat[i][j].p;//很平常的01状态转移
    for(int j=0;j<=n-a[i].v;j++)
    if(f[j]!=-1)//恰好背包的判断,这种附件组合满足题意
    {
    cnt[i]++;
    V[i][cnt[i]]=j+a[i].v;
    P[i][cnt[i]]=f[j]+a[i].v*a[i].p;//把此情况存在主件i的分组中,为分组背包做好处理
    }
    }
    if(!a[i].q)//只买主件
    {
    cnt[i]++;
    V[i][cnt[i]]=a[i].v;
    P[i][cnt[i]]=a[i].v*a[i].p;//存储
    }
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<=m;i++)
    for(int j=n;j>=0;j--)
    for(int k=1;k<=cnt[i];k++)
    if(j>=V[i][k])
    f[j]=max(f[j],f[j-V[i][k]]+P[i][k]);//分组背包的计算
    for(int i=0;i<=n;i++)
    ans=max(ans,f[i]);
    printf("%d",ans);//输出
    return 0;
    }

  • 1
    @ 2019-07-31 11:15:00

    01背包变形,主要是处理好主从的关系,个人在输入数据的时候把主件和附件放在一起,然后循环每个主件,讨论5种情况(不买主件、仅买主件、买主件和第一附件、买主件和第二附件、买主件和两附件)选最大值,优化到一维数组。

    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    int major[60],mNum=0,V[180],P[180],v,p,q,N,m,index,f[32100];
    int main(){
        cin>>N>>m;
        for(int i=0;i<m;i++){
            cin>>v>>p>>q;
            if(q==0){//主件 
                index=i*3;
                major[mNum++]=index;
            }else{//附件数据放到主件后 
                index=(q-1)*3+1;//对应主件位置+1 
                if(P[index]>0)//已有一个附件 
                    index++;
            }
            V[index]=v;
            P[index]=p;
        }
            
        for(int i=0;i<mNum;i++){//遍历每一个主件
            index=major[i];//取主件序号 
            for(int j=N;j>=V[index];j--){
                int rest=j-V[index];//买主件后剩余钱 
                int mV=V[index]*P[index];//主件价格与重要度乘积
                int cmp[5]={f[j],f[rest]+mV};//不买/仅买主件 
                if(P[index+1]>0){//有附件
                    int rest1=rest-V[index+1];//买第一附件后剩余钱
                    if(rest1>=0)//买得起第一附件 
                        cmp[2]=f[rest1]+mV+V[index+1]*P[index+1];//买主件和第一附件
                    if(P[index+2]>0){//有第二附件
                        int rest2=rest-V[index+2];//买第二附件后剩余钱
                        if(rest2>=0){//买得起第二附件 
                            cmp[3]=f[rest2]+mV+V[index+2]*P[index+2];//买主件和第二附件
                            int rest12=rest1-V[index+2];//买两附件后剩余钱
                            if(rest12>=0)//买得起两附件 
                                cmp[4]=f[rest12]+mV+V[index+1]*P[index+1]+V[index+2]*P[index+2];//买主件和两附件
                        } 
                    } 
                }
                f[j]=*max_element(cmp,cmp+5);
            }
        } 
        cout<<f[N]<<endl;
        return 0;
    }
    
    
  • 1
    @ 2019-03-03 11:56:54

    将输入处理一下,将附件和对应的主件放在一起,可以简化问题。

    #include<bits/stdc++.h>
    using namespace std;
    int N,m,tv,tp,tq,v[250],p[250],a[250][32000];
    
    int dp(int i,int j){
        int &ans = a[i][j];
        if(ans) return ans;
        if(i==0) return 0;
        if(j>=v[i]&&v[i]!=0){
            if(i%4==0)
                ans = max(dp(i-4,j),dp(i-1,j-v[i])+v[i]*p[i]);
            else
                ans = max(dp(i-1,j),dp(i-1,j-v[i])+v[i]*p[i]);
        }else{
            if(i%4==0) ans = dp(i-4,j);
            else ans = dp(i-1,j);
        }
        return ans;
    }
    int main(){
        scanf("%d%d",&N,&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&tv,&tp,&tq);
            if(tq==0){
                v[i*4] = tv;
                p[i*4] = tp;
            } else{
                int cur = tq*4-1;
                while(v[cur]) cur--;
                v[cur] = tv;
                p[cur] = tp;
            }
        }
        printf("%d",dp(m*4,N));
    }
    
    
  • 1
    @ 2018-10-30 18:20:45
    #include <iostream>
    #include <algorithm>
    using namespace std;
    int N, m;//N总钱数,m物品件数
    long long v[60], w[60],q[60];//v钱数,w重要度,q主件和附件编号
    long long vgroup[60][3] = { 0 }, wgroup[60][3] = { 0 };//第0列是主件,第1列是第一个附件,第1列是第二个附件的属性
    int index[60] = { 0 };//记录编号为i的物品附件的个数
    long long maxvalue[32000] = { 0 };
    int main()
    {
        int i, j;
        cin >> N >> m;
        for (i = 1; i <= m; i++)
        {
            cin >> v[i] >> w[i] >> q[i];//读入数据
            if (q[i] == 0)  //主件的数据移动到新的数组的第0列
            {
                vgroup[i][0] = v[i];
                wgroup[i][0] = w[i];
            }
            if (q[i] > 0)//记录附件属性
            {
                index[q[i]]++;
                vgroup[q[i]][index[q[i]]] = v[i];
                wgroup[q[i]][index[q[i]]] = w[i];
            }
        }
        for (i = 1; i <= m; i++)    //DP
            for (j = N; j >= 1; j--)
                if (q[i] == 0)
                {
                    
                    if (vgroup[i][0] <= j) //取主件
                        maxvalue[j] = max(maxvalue[j - vgroup[i][0]]+vgroup[i][0]*wgroup[i][0], maxvalue[j]);
                    if (vgroup[i][0] + vgroup[i][1] <= j)//取主件加附件1
                        maxvalue[j] = max(maxvalue[j - vgroup[i][0] - vgroup[i][1]] + vgroup[i][0] * wgroup[i][0] + vgroup[i][1] * wgroup[i][1], maxvalue[j]);
                    if (vgroup[i][0] + vgroup[i][2] <= j)//取主件加附件2
                        maxvalue[j] = max(maxvalue[j - vgroup[i][0] - vgroup[i][2]] + vgroup[i][0] * wgroup[i][0] + vgroup[i][2] * wgroup[i][2], maxvalue[j]);
                    if (vgroup[i][0] + vgroup[i][1] + vgroup[i][2] <= j)//全部取
                        maxvalue[j] = max(maxvalue[j - vgroup[i][0] - vgroup[i][1]- vgroup[i][2]] + vgroup[i][0] * wgroup[i][0] + vgroup[i][1] * wgroup[i][1] + vgroup[i][2] * wgroup[i][2], maxvalue[j]);
                }
        cout << maxvalue[N] << endl;
        system("pause");
        return 0;
    }
    
  • 0
    @ 2019-07-10 14:33:49
    #include <bits/stdc++.h>
    using namespace std;
    int n, m;
    int cost[100];
    int val[100];
    vector<int> major;
    vector<int> minor[100];
    int dp[32010];
    int dp2[32010];
    
    int main() {
        scanf("%d%d", &n, &m);
        for(int i = 0; i < m; ++i) {
            int v, p, q;
            scanf("%d%d%d", &v, &p, &q);
            cost[i] = v;
            val[i] = v * p;
            if(q == 0) {
                major.push_back(i);
            } else {
                minor[q-1].push_back(i);
            }
        }
        memset(dp, 0, sizeof dp);
        for(int i = 0; i < major.size(); ++i) {
            int cur = major[i];
    
            // initialize dp2
            for(int v = 0; v <= n; ++v) {
                if(v < cost[cur]) 
                    dp2[v] = -1;
                else 
                    dp2[v] = dp[v - cost[cur]] + val[cur];
            }
            for(int j = 0; j < minor[cur].size(); ++j) {
                int idx = minor[cur][j];
                for(int v = n; v >= cost[idx] + cost[cur]; --v) {
                    dp2[v] = max(dp2[v], dp2[v - cost[idx]] + val[idx]);
                }
            }
            for(int v = 0; v <= n; ++v) {
                dp[v] = max(dp[v], dp2[v]);
            }
        }
        printf("%d\n", dp[n]);
    }
    
  • 0
    @ 2017-12-02 15:21:09

    #include<bits/stdc++.h>
    using namespace std;
    struct node
    {
    int tot;
    int v[5];
    int w[5];
    }d[61];
    long long f[32001];
    int n,m;
    int main()
    { memset(f,0,sizeof(f));
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    d[i].tot=0;
    for (int i=1;i<=m;i++)
    for (int j=0;j<=5;j++)
    d[i].v[j]=10005;
    for (int i=1;i<=m;i++)
    {
    int a,b,c;
    cin>>a>>b>>c;
    if (c==0)
    d[i].v[0]=a,d[i].w[0]=b*a;
    else
    d[c].tot++,d[c].v[d[c].tot]=a,d[c].w[d[c].tot]=a*b;
    }
    for (int i=1;i<=m;i++)
    for (int j=n;j>=0;j--)
    {
    if (j-d[i].v[0]>=0)
    f[j]=max(f[j-d[i].v[0]]+d[i].w[0],f[j]);
    if (j-d[i].v[1]-d[i].v[0]>=0&&d[i].tot>=1)
    f[j]=max(f[j-d[i].v[0]-d[i].v[1]]+d[i].w[0]+d[i].w[1],f[j]);
    if (j-d[i].v[2]-d[i].v[0]>=0&&d[i].tot>=2)
    f[j]=max(f[j-d[i].v[0]-d[i].v[2]]+d[i].w[0]+d[i].w[2],f[j]);
    if (j-d[i].v[1]-d[i].v[0]-d[i].v[2]>=0&&d[i].tot>=2)
    f[j]=max(f[j-d[i].v[0]-d[i].v[1]-d[i].v[2]]+d[i].w[0]+d[i].w[1]+d[i].w[2],f[j]);
    }
    cout<<f[n]<<endl;
    return 0;
    }

  • 0
    @ 2017-11-07 21:07:05

    最多只有两件副的,所以傻傻的暴力下下就行,一定要注意0,1和等号

    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<cstdio>
    #include<cstdlib>
    using namespace std;
    int n,m,v,p,q;
    int imp[108][3],vo[108][3],f[108][40000];
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>v>>p>>q;
            if(!q)
                {vo[i][0]=v; imp[i][0]=p;}
            else
            {
                if(!vo[q][1])
                    {vo[q][1]=v; imp[q][1]=p;}
                else
                    {vo[q][2]=v; imp[q][2]=p;}
            }
        }
        for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            if(j-vo[i][0]>=0)
            {
                f[i][j]=max(f[i-1][j],f[i-1][j-vo[i][0]]+vo[i][0]*imp[i][0]);
                if(j-vo[i][0]-vo[i][1]>=0)
                    f[i][j]=max(f[i][j],f[i-1][j-vo[i][0]-vo[i][1]]+vo[i][0]*imp[i][0]+vo[i][1]*imp[i][1]);
                if(j-vo[i][0]-vo[i][2]>=0)
                    f[i][j]=max(f[i][j],f[i-1][j-vo[i][0]-vo[i][2]]+vo[i][0]*imp[i][0]+vo[i][2]*imp[i][2]);
                if(j-vo[i][0]-vo[i][1]-vo[i][2]>=0)
                    f[i][j]=max(f[i][j],f[i-1][j-vo[i][0]-vo[i][1]-vo[i][2]]+vo[i][0]*imp[i][0]+vo[i][1]*imp[i][1]+vo[i][2]*imp[i][2]);
            }
            else
                f[i][j]=f[i-1][j];
        }
        cout<<f[m][n];
        return 0;
    }
    
  • 0
    @ 2017-07-12 15:32:45

    树形动归
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    inline const void read(int &a)
    {
    a=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')
    {
    a=a*10+c-'0';
    c=getchar();
    }
    }
    class article
    {
    public:
    int v,p,left,right;//价 权
    }t[61];
    int n,m,d=0;
    int to[1000],nex[1000],ans[61][3201];
    bool cal[61][3201];
    int dfs(int p,int rest)
    {
    if(cal[p][rest])return ans[p][rest];//防止重复计算
    cal[p][rest]=true;
    if(rest>=t[p].v)ans[p][rest]=t[p].v*t[p].p;//只取自己
    if(t[p].left&&t[p].right)//左右儿子和自己都取
    {
    for(int i=0;i<=rest-t[p].v;i++)//给左儿子分担i,右儿子分担rest-i-t[p].v
    ans[p][rest]=max(ans[p][rest],dfs(t[p].left,i)+dfs(t[p].right,rest-t[p].v-i)+t[p].v*t[p].p);
    }
    if(t[p].left)//取左儿子与自己
    if(rest>=t[p].v)ans[p][rest]=max(ans[p][rest],dfs(t[p].left,rest-t[p].v)+t[p].v*t[p].p);
    if(t[p].right)//取右儿子与自己或只取右儿子
    {
    ans[p][rest]=max(ans[p][rest],dfs(t[p].right,rest));
    if(rest>=t[p].v)ans[p][rest]=max(ans[p][rest],dfs(t[p].right,rest-t[p].v)+t[p].v*t[p].p);
    }
    return ans[p][rest];
    }
    int main()
    {
    //freopen("测试数据.txt","r",stdin);
    memset(nex,0,sizeof(nex));
    memset(ans,0,sizeof(ans));
    memset(cal,false,sizeof(cal));
    read(n);read(m);
    n/=10;
    for(int i=0;i<=m;i++)t[i].v=t[i].left=t[i].right=0;
    for(int i=1;i<=m;i++)
    {
    int k;
    read(t[i].v);read(t[i].p);read(k);
    t[i].v/=10;d++;
    if(t[k].left)
    {
    k=t[k].left;
    while(t[k].right)k=t[k].right;
    t[k].right=i;
    }
    else t[k].left=i;
    }
    printf("%d",dfs(0,n)*10);
    return 0;
    }

  • 0
    @ 2017-04-08 14:20:59

    #1 Accepted 1ms 200.0KiB
    #2 Accepted 1ms 200.0KiB
    #3 Accepted 1ms 208.0KiB
    #4 Accepted 1ms 256.0KiB
    #5 Accepted 2ms 204.0KiB
    #6 Accepted 2ms 204.0KiB
    #7 Accepted 2ms 256.0KiB
    #8 Accepted 3ms 196.0KiB
    #9 Accepted 5ms 200.0KiB
    #10 Accepted 1ms 256.0KiB
    很简单的思路。

    var
      w, v:array[1..60, 1..3] of longint;
      fu:array[1..60, 1..3] of longint;
      f:array[0..3200] of longint;
      p:array[1..60] of longint;
      n, x, k, m, fm, tw, tv, i, j:longint;
    begin
      readln(x, n);
      x:=x div 10;
      fillchar(w, sizeof(w), 0);
      fillchar(v, sizeof(v), 0);
      fillchar(fu, sizeof(fu), 0);
      fillchar(p, sizeof(p), 0);
      m:=0;
      fm:=0;
      for i:=1 to n do begin
        readln(tw, tv, k);
        if k=0 then begin
          inc(m);
          w[m, 1]:=tw div 10;
          v[m, 1]:=tw*tv div 10;
          p[m]:=i
        end
        else begin
          inc(fm);
          fu[fm, 1]:=tw div 10;
          fu[fm, 2]:=tw*tv div 10;
          fu[fm, 3]:=k
        end;
      end;
      for i:=1 to fm do
        for j:=1 to m do if p[j]=fu[i, 3] then if w[j, 2]=0 then begin
          w[j, 2]:=fu[i, 1];
          v[j, 2]:=fu[i, 2];
          break
        end
        else begin
           w[j, 3]:=fu[i, 1];
           v[j, 3]:=fu[i, 2];
           break
        end;
      fillchar(f, sizeof(f), 0);
      for i:=1 to m do
        for j:=x downto w[i, 1] do begin
          if f[j-w[i, 1]]+v[i, 1]>f[j] then f[j]:=f[j-w[i, 1]]+v[i, 1];
          if (j-w[i, 1]-w[i, 2]>-1) and (f[j-w[i, 1]-w[i, 2]]+v[i, 1]+v[i, 2]>f[j]) then f[j]:=f[j-w[i, 1]-w[i, 2]]+v[i, 1]+v[i, 2];
          if (j-w[i, 1]-w[i, 3]>-1) and (f[j-w[i, 1]-w[i, 3]]+v[i, 1]+v[i, 3]>f[j]) then f[j]:=f[j-w[i, 1]-w[i, 3]]+v[i, 1]+v[i, 3];
          if (j-w[i, 1]-w[i, 2]-w[i, 3]>-1) and (f[j-w[i, 1]-w[i, 2]-w[i, 3]]+v[i, 1]+v[i, 2]+v[i, 3]>f[j]) then f[j]:=f[j-w[i, 1]-w[i, 2]-w[i, 3]]+v[i, 1]+v[i, 2]+v[i, 3]
        end;
      write(f[x]*10)
    end.
    
    

    先读入,在一点点处理。因为价格和价值都是10的整倍数,因此可以先除10,最后再乘10。

  • 0
    @ 2017-01-19 22:09:04

    //好不爽,被编号坑了
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;

    int f[61][32001],cn[61],cx[61],n,m,g=0;

    struct node1
    {
    int v,p,q;
    }a[61];

    struct node2
    {
    int v,p;
    }c[61][5];

    int main()
    {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
    scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q);
    a[i].p*=a[i].v;
    }
    memset(cn,0,sizeof(cn));
    for (int i=1;i<=m;i++)
    {
    if (a[i].q==0)
    {
    g++;
    cx[i]=g;
    cn[g]++;
    c[g][cn[g]].p=a[i].p;
    c[g][cn[g]].v=a[i].v;
    }
    else
    {
    int x=cx[a[i].q];
    cn[x]++;
    c[x][cn[x]].p=c[x][1].p+a[i].p;
    c[x][cn[x]].v=c[x][1].v+a[i].v;
    if (cn[x]==3)
    {
    cn[x]++;
    c[x][cn[x]].p=c[x][2].p+c[x][3].p-c[x][1].p;
    c[x][cn[x]].v=c[x][2].v+c[x][3].v-c[x][1].v;
    }
    }
    }
    memset(f,0,sizeof(f));
    for (int i=1;i<=g;i++)
    for (int j=n;j>=0;j--)
    for (int k=1;k<=cn[i];k++)
    {
    f[i][j]=max(f[i][j],f[i-1][j]);
    if (j>=c[i][k].v)
    f[i][j]=max(f[i][j],f[i-1][j-c[i][k].v]+c[i][k].p);
    }
    printf("%d\n",f[g][n]);
    }

    • @ 2017-01-19 22:10:00

      还我通过率!!!

    • @ 2017-01-19 22:14:53

      这么H2O的题WA了这么多次

  • 0
    @ 2016-11-21 01:00:27

    想知道用树形dp怎么解决这道题

  • 0
    @ 2016-10-19 18:57:09

    #include <iostream>
    #include <vector>
    #include <map>

    using namespace std;

    #define MAXM 32001
    #define MAXN 61

    int m,n;
    int f[MAXM],w[MAXN],c[MAXN],o[MAXN];
    map < int,vector <int> >p;

    int main()
    {
    int i,j;
    cin>>m>>n;
    for(i=1;i<=n;++i)
    {
    cin>>w[i]>>c[i]>>o[i];
    if(o[i]!=0)p[o[i]].push_back(i);
    }
    for(i=1;i<=n;++i)
    {
    if(o[i])continue;
    for(j=m;j>=w[i];--j)
    {
    int a=w[i]*c[i],b=j-w[i];
    switch(p[i].size())
    {
    case 2:
    if(b-w[p[i][0]]-w[p[i][1]]>=0)
    f[j]=max(f[j],f[b-w[p[i][0]]-w[p[i][1]]]+a+w[p[i][0]]*c[p[i][0]]+w[p[i][1]]*c[p[i][1]]);
    if(b-w[p[i][1]]>=1)
    f[j]=max(f[j],f[b-w[p[i][1]]]+a+w[p[i][1]]*c[p[i][1]]);
    case 1:
    if(b-w[p[i][0]]>=0)
    f[j]=max(f[j],f[b-w[p[i][0]]]+a+w[p[i][0]]*c[p[i][0]]);
    case 0:
    f[j]=max(f[j],f[b]+a);
    }
    }
    }
    cout<<f[m];
    return 0;
    }

  • 0
    @ 2016-09-10 09:15:09

    垃圾……

    #include <set>
    #include <map>
    #include <list>
    #include <cmath>
    #include <ctime>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <cctype>
    #include <cstdio>
    #include <string>
    #include <vector>
    #include <cassert>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #define maxn (1000 + 20)
    #define inf 0x3f3f3f3f
    #define pi acos(-1.0)
    using namespace std;
    typedef long long int LLI;
    
    struct node {
        int v;
        int p;
        int q;
        int vp;
        node() {
            v = -1;
        }
    };
    node zhujian[maxn],fujian1[maxn],fujian2[maxn];
    vector<node> ans[maxn];
    int dp[32000 + 50];
    int main() {
    //    freopen("in.txt","r",stdin);
    //    freopen("out1.txt","w",stdout);
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= m; i ++) {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            if(z == 0)  {
                zhujian[i].v = x;
                zhujian[i].p = y;
                zhujian[i].q = i;
                zhujian[i].vp = x * y;
            } else {
                if(fujian1[z].v == -1) {
                    fujian1[z].v = x;
                    fujian1[z].p = y;
                    fujian1[z].vp = x * y;
                } else {
                    fujian2[z].v = x;
                    fujian2[z].p = y;
                    fujian2[z].vp = x * y;
                }
            }
        }
        int cnt = m;
        for(int i = 1; i <= m; i ++) {
            if(zhujian[i].v == -1)  continue;
            if(fujian1[i].v != -1) {
                zhujian[++cnt].vp = fujian1[i].vp + zhujian[i].vp;
                zhujian[cnt].v = fujian1[i].v + zhujian[i].v;
                zhujian[cnt].q = i;
            }
            if(fujian2[i].v != -1) {
                zhujian[++cnt].v = fujian2[i].v + zhujian[i].v;
                zhujian[cnt].vp = fujian2[i].vp + zhujian[i].vp;
                zhujian[cnt].q = i;
                zhujian[++cnt].v = fujian2[i].v + zhujian[i].v + fujian1[i].v;
                zhujian[cnt].vp = fujian2[i].vp + zhujian[i].vp + fujian1[i].vp;
                zhujian[cnt].q = i;
            }
        }
        for(int i = 1; i <= cnt; i ++) {
            if(zhujian[i].v == -1)  continue;
            int k = zhujian[i].q;
            ans[k].push_back(zhujian[i]);
    //    printf("%d %d %d\n",zhujian[i].v,zhujian[i].vp,zhujian[i].q);
        }
        for(int i = 0; i < 60; i ++) {
            if(ans[i].size() == 0)  continue;
            for(int j = n; j >= 0; j --) {
                for(int k = 0; k < ans[i].size(); k ++) {
                    if(j < ans[i][k].v) continue;
                    dp[j] = max(dp[j],dp[j - ans[i][k].v] + ans[i][k].vp);
                }
            }
        }
    //    for(int i = 0; i <= 60; i ++) {
    //        if(ans[i].size() == 0)  continue;
    //        for(int k = 0; k < ans[i].size(); k ++) {
    //            printf("%d %d %d\n",ans[i][k].v,ans[i][k].p,ans[i][k].q);
    //        }
    //        printf("\n");
    //    }
        printf("%d\n",dp[n]);
        return 0;
    }
    
  • 0
    @ 2016-08-25 20:56:56

    因为最多2个附属 用捆绑法 共3种情况
    不能开始时将主附捆绑作为新的一个去枚举,这样会有重复,需枚举主见即可
    uses math;
    type re=record
    a,b:longint;
    end;
    var
    i,j,k,m,n,j1:longint;
    a,b,d:array[0..200]of longint;
    c:array[0..200]of re;
    f:array[0..35000]of longint;
    begin
    readln(n,m);
    fillchar(c,sizeof(c),0);
    j1:=0;
    for i:=1 to m do
    begin
    read(a[i]);
    read(j);
    read(k);
    d[i]:=k;
    b[i]:=a[i]*j;
    if k>0 then
    if c[k].a<>0 then
    c[k].b:=i else c[k].a:=i;
    end;
    for i:=1 to m do
    for j:=n downto a[i] do
    if d[i]=0 then
    begin
    f[j]:=max(f[j],f[j-a[i]]+b[i]);
    if (c[i].a<>0) and (c[i].b<>0) and (j-a[i]-a[c[i].a]-a[c[i].b]>=0) then
    f[j]:=max(f[j],f[j-a[i]-a[c[i].a]-a[c[i].b]]+b[i]+b[c[i].a]+b[c[i].b]);
    if (c[i].a<>0) and (j-a[i]-a[c[i].a]>=0) then
    f[j]:=max(f[j],f[j-a[i]-a[c[i].a]]+b[i]+b[c[i].a]);
    if (c[i].b<>0) and (j-a[i]-a[c[i].b]>=0) then
    f[j]:=max(f[j],f[j-a[i]-a[c[i].b]]+b[i]+b[c[i].b]);
    end;
    writeln(f[n]);
    end.

  • 0
    @ 2016-08-14 10:25:39

    DP
    ```
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<vector>
    #include<queue>
    using namespace std;
    const int maxn = 50000 + 5;
    const int INF = 1000000000;
    struct Node{
    int v, w;
    };
    int n, m, d[maxn];

    vector<Node> vec[maxn];

    void init(){
    int tot = 0, x, y, z;

    cin >> n >> m;
    for(int i = 1; i <= m; i++){
    cin >> x >> y >> z;
    if(z) vec[z].push_back((Node){x, y});
    else vec[i].push_back((Node){x, y});
    }
    for(int i = 0; i <= n; i++)
    d[i] = 0;

    }
    void work(){
    for(int i = 1; i <= m; i++){
    if(vec[i].empty()) continue;
    for(int j = n; j >= 0; j--){
    if(j >= vec[i][0].v){
    //只买主件
    d[j] = max(d[j], d[j-vec[i][0].v] + vec[i][0].w * vec[i][0].v);
    //只买某一个附件
    for(int k = 1; k < vec[i].size(); k++){
    if(j >= vec[i][0].v + vec[i][k].v)
    d[j] = max(d[j], d[j-vec[i][0].v-vec[i][k].v] + vec[i][k].w * vec[i][k].v + vec[i][0].w * vec[i][0].v);
    //两个附件一起
    if(vec[i].size() > 2 && j >= vec[i][0].v + vec[i][1].v + vec[i][2].v)
    d[j] = max(d[j], d[j-vec[i][0].v-vec[i][1].v-vec[i][2].v] + vec[i][1].w * vec[i][1].v + vec[i][2].w * vec[i][2].v + vec[i][0].w * vec[i][0].v);

    }
    }
    }
    }
    }
    int main(){
    init();
    work();
    cout << d[n];
    return 0;
    }
    ```

  • 0
    @ 2016-08-02 13:37:45

    钦定与暴力与dp
    ```c++
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    int n, m;
    int v[100], p[100], q[100];

    struct p {
    int to, next;
    }edge[100];
    int head[100], top = 0;
    int dp[32005];

    void push(int i, int j)
    {
    edge[++top].to = j;
    edge[top].next = head[i];
    head[i] = top;
    }

    int main()
    {
    scanf("%d%d", &n, &m);
    n /= 10;
    for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &v[i], &p[i], &q[i]);
    v[i] /= 10;
    if (q[i])
    push(q[i], i);
    }
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= m; i++){
    for (int j = n; j >= v[i]; j--) if (!q[i]){
    int pst = dp[j];
    //if (dp[j-v[i]]+p[i]*v[i] >= dp[j]) {
    dp[j] = dp[j-v[i]]+p[i]*v[i];
    int choice[4], tp = 0;
    for (int k = head[i]; k; k = edge[k].next)
    choice[++tp] = edge[k].to;
    if (tp >= 1 && j-v[i]-v[choice[1]] >= 0)
    dp[j] = max(dp[j], dp[j-v[i]-v[choice[1]]]+p[i]*v[i]+p[choice[1]]*v[choice[1]]);
    if (tp >= 2) {
    if (j-v[i]-v[choice[2]] >= 0)
    dp[j] = max(dp[j], dp[j-v[i]-v[choice[2]]]+p[i]*v[i]+p[choice[2]]*v[choice[2]]);
    if (j-v[i]-v[choice[1]]-v[choice[2]] >= 0)
    dp[j] = max(dp[j], dp[j-v[i]-v[choice[1]]-v[choice[2]]]+p[i]*v[i]+p[choice[1]]*v[choice[1]]+p[choice[2]]*v[choice[2]]);
    }
    if (tp >= 3) {
    if (j-v[i]-v[choice[3]] >= 0)
    dp[j] = max(dp[j], dp[j-v[i]-v[choice[3]]]+p[i]*v[i]+p[choice[3]]*v[choice[3]]);
    if (j-v[i]-v[choice[3]]-v[choice[2]] >= 0)
    dp[j] = max(dp[j], dp[j-v[i]-v[choice[3]]-v[choice[2]]]+p[i]*v[i]+p[choice[3]]*v[choice[3]]+p[choice[2]]*v[choice[2]]);
    if (j-v[i]-v[choice[3]]-v[choice[1]] >= 0)
    dp[j] = max(dp[j], dp[j-v[i]-v[choice[3]]-v[choice[1]]]+p[i]*v[i]+p[choice[3]]*v[choice[3]]+p[choice[1]]*v[choice[1]]);
    if (j-v[i]-v[choice[3]]-v[choice[2]]-v[choice[1]] >= 0)
    dp[j] = max(dp[j], dp[j-v[i]-v[choice[3]]-v[choice[2]]-v[choice[1]]]+p[i]*v[i]+p[choice[1]]*v[choice[1]]+p[choice[3]]*v[choice[3]]+p[choice[2]]*v[choice[2]]);
    }
    //}
    dp[j] = max(pst, dp[j]);
    }
    }

    cout << dp[n]*10 <<endl;
    return 0;
    }
    ```

信息

ID
1313
难度
6
分类
动态规划 | 背包 点击显示
标签
递交数
8275
已通过
2448
通过率
30%
被复制
14
上传者