2DBackPack

#include<iostream>
using namespace std;
const int num = 4; //物品数量
const int weight = 13; //背包最大承载重量
const int volume = 8; //背包最大承载体积
int v[num + 1] = {0, 12, 11, 9, 8}; //物品价值
int w[num + 1] = {0, 8, 6, 4, 3}; //物品重量
int c[num + 2] = {0, 1, 2, 3, 4}; //物品体积
int m[num + 1][weight + 1][volume + 1] = {0};
//m[i][j][k]:装前i个物品总重量不超过j总体积不超过k的最大价值
int s[num + 1][weight + 1][volume + 1] = {0};
//s[i][j][k]:装前i个物品总重量不超过j总体积不超过k的装入物品的最大标号
int main(){
    for(int i = 1; i <= num; i++){
        for(int j = 1; j <= weight; j++){
            for(int k = 1; k <= volume; k++){
                if( j >= w[i] && k >= c[i] && m[i-1][j-w[i]][k-c[i]] + v[i] > m[i-1][j][k]){
                    m[i][j][k] = m[i-1][j-w[i]][k-c[i]] + v[i];
                    s[i][j][k] = i;
                }
                else{
                    m[i][j][k] = m[i-1][j][k];
                    s[i][j][k] =  s[i-1][j][k];
                }
            }
        }
    }
    //时间复杂度O(num*weight*volume)
    cout<<m[num][weight][volume]<<endl;
    return 0;
}