Advertisement
ambition-xx

01BackPack

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