【算法】二维费用背包问题

三维数组实现

#include <iostream>
using namespace std;
const int N = 101;
int n,V, m;
int v[N], w[N],c[N];//v 体积 w 重量 c 价值 
int f[N][N][N];
int main() {
    cin  >>V>> m>> n;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]>>c[i];
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= V; j ++ ) {
        	for(int k=1;k<=m ;k++){
            	f[i][j][k] = f[i - 1][j][k];
            	if (j >= v[i]&&k>=w[i]) f[i][j][k]= max(f[i][j][k],f[i-1][j-v[i]][k-w[i]] + c[i]);
        }
	}
    cout << f[n][V][m];
    return 0;
}

二维数组实现（空间优化）

#include <iostream>

using namespace std;

const int N = 1010, K = 110;

int n, V, M;

int v1[N], v2[N], w[N];
int f[K][K];

int main()
{
    //input
    cin >> n >> V >> M;
    for (int i = 1; i <= n; ++ i) cin >> v1[i] >> v2[i] >> w[i];
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = V; j >= v1[i]; -- j)
        {
            for (int k = M; k >= v2[i]; -- k)
            {
                f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + w[i]);
            }
        }
    }
    cout << f[V][M] << endl;
    return 0;
}