daily pastebin goal
36%
SHARE
TWEET

Untitled

a guest Oct 19th, 2018 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2. * 某旅行者外出, 需要将5件物品装入包中. 包的总容量是10kg, 物品重量及价值如表. 问如何装这些物品, 才能使得总价值最大?
  3. * A B C D E
  4. * 4 5 6 2 2
  5. * 6 4 5 3 6
  6. */
  7.  
  8. function calc(n, m, w, v){
  9.     w.unshift(0);
  10.     v.unshift(0);
  11.     let s = [...Array(n + 1)].map(x=>[...Array(m + 1)].map(()=>0));
  12.     for (let i = 0; i <= n; i++) {
  13.         for (let j = 0; j <= m; j++) {
  14.             if (i === 0 || j === 0){
  15.                 s[i][j] = 0;
  16.             }
  17.             else if (j - w[i] < 0) {
  18.                 s[i][j] = s[i - 1][j];
  19.             }
  20.             else {
  21.                 s[i][j] = Math.max(s[i - 1][j], s[i - 1][j - w[i]] + v[i]);
  22.             }
  23.         }
  24.     }
  25.     return s[n][m];    
  26. }
  27.  
  28. let maxValue = calc(5, 10, [4,5,6,2,2], [6,4,5,3,6]);
  29. console.info(maxValue);
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top