2551矩阵

admin

【问题描述】
有一个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(n^2V）一样TLE啊

admin

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. */

复制代码