Advertisement
ambition-xx

2DBackPack

Nov 14th, 2020
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.07 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. const int num = 4; //物品数量
  4. const int weight = 13; //背包最大承载重量
  5. const int volume = 8; //背包最大承载体积
  6. int v[num + 1] = {0, 12, 11, 9, 8}; //物品价值
  7. int w[num + 1] = {0, 8, 6, 4, 3}; //物品重量
  8. int c[num + 2] = {0, 1, 2, 3, 4}; //物品体积
  9. int m[num + 1][weight + 1][volume + 1] = {0};
  10. //m[i][j][k]:装前i个物品总重量不超过j总体积不超过k的最大价值
  11. int s[num + 1][weight + 1][volume + 1] = {0};
  12. //s[i][j][k]:装前i个物品总重量不超过j总体积不超过k的装入物品的最大标号
  13. int main(){
  14.     for(int i = 1; i <= num; i++){
  15.         for(int j = 1; j <= weight; j++){
  16.             for(int k = 1; k <= volume; k++){
  17.                 if( j >= w[i] && k >= c[i] && m[i-1][j-w[i]][k-c[i]] + v[i] > m[i-1][j][k]){
  18.                     m[i][j][k] = m[i-1][j-w[i]][k-c[i]] + v[i];
  19.                     s[i][j][k] = i;
  20.                 }
  21.                 else{
  22.                     m[i][j][k] = m[i-1][j][k];
  23.                     s[i][j][k] =  s[i-1][j][k];
  24.                 }
  25.             }
  26.         }
  27.     }
  28.     //时间复杂度O(num*weight*volume)
  29.     cout<<m[num][weight][volume]<<endl;
  30.     return 0;
  31. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement