华师一附中OI组

标题: 2551矩阵 [打印本页]
作者: admin    时间: 2021-10-14 14:46
标题: 2551矩阵
【问题描述】
有一个n×m的矩阵，你从左上角走到右下角，只能向下和向右走。
每个点上有一个重量v(i,j)价值w(i,j)的物品，你有一个容量为S的背包，经过一个点你可以将此点的物品放入背包，求最大能得到的价值。
【输入】
输入文件matrix.in。
第一行三个数n,m,S。
下面n行，每行m个数，第i+1行第j个数表示v(i,j)。
下面n行，每行m个数，第i+n+1行第j个数表示w(i,j)。
【输出】
输出文件matrix.out。
一行一个数表示最大的价值。
【输入输出样例】
matrix.in        matrix.out
3 4 5
1 2 1 1
2 3 1 2
3 2 2 2
2 3 4 2
1 4 5 1
10 1 2 1        14
【数据说明】
30%:n×m≤50,S≤100
60%:n,m≤100,S≤200
100%:n,m≤400,0≤v(i,j),w(i,j)≤1000,S≤400
作者: admin    时间: 2021-10-14 14:47
fi,j,k表示走到(i,j)、背包剩余容量为k时的最大价值。
fi,j由fi-1,j和fi,j-1按普通01背包的方法转移。
时间复杂度O(N2V)，空间O(N2V)。
按行或对角线滚动数组，空间O(NV)。

  1. #include<iostream>
  2. #include<cstdio>
  3. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  4. using namespace std;
  5. const int N=500,INF=1000010000;
  6. int n,m,ans,c[N][N],w[N][N],S,f[2][N][N];
  7. int main()
  8. {
  9.         freopen("matrix.in","r",stdin);
  10.         freopen("matrix.out","w",stdout);
  11.         scanf("%d%d%d",&n,&m,&S);
  12.         FOR(i,1,n)FOR(j,1,m) scanf("%d",&c[i][j]);
  13.         FOR(i,1,n)FOR(j,1,m) scanf("%d",&w[i][j]);
  14.         FOR(i,0,1)FOR(j,0,m)FOR(k,0,S) f[i][j][k]=-INF;
  15.         f[0][1][0]=0;
  16.         FOR(i,1,n)FOR(j,1,m)
  17.         {
  18.                 FOR(k,0,S)
  19.                 {
  20.                         f[i&1][j][k]=max(f[i&1][j-1][k],f[i&1^1][j][k]);
  21.                         if(k>=c[i][j])
  22.                                 {
  23.                                         f[i&1][j][k]=max(f[i&1][j][k],f[i&1][j-1][k-c[i][j]]+w[i][j]);
  24.                                         f[i&1][j][k]=max(f[i&1][j][k],f[i&1^1][j][k-c[i][j]]+w[i][j]);
  25.                                 }
  26.                         if(f[i&1][j][k]<0) f[i&1][j][k]=-INF;
  27.                 }
  28.                 //cout<<i<<' '<<j<<endl;
  29.                 //FOR(k,0,S) cout<<f[i&1][j][k]<<' ';cout<<endl;
  30.         }
  31.         FOR(k,1,S) ans=max(ans,f[n&1][m][k]);
  32.         printf("%d",ans);
  33. }/*
  34. 3 3 2
  35. 0 1 1
  36. 1 1 2
  37. 2 1 0
  38. 0 2 4
  39. 2 3 4
  40. 4 3 0
  41. */
复制代码


作者: 周陈诚    时间: 2021-10-14 16:37
admin 发表于 2021-10-14 14:47
fi,j,k表示走到(i,j)、背包剩余容量为k时的最大价值。
fi,j由fi-1,j和fi,j-1按普通01背包的方法转移。
时 ...

但是O(n^2V）一样TLE啊



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2