자바 스크립트 배낭 알고리즘 - 가장 낮은 값으로 찾기

Question

나는 배낭 문제의 구현을 발견했습니다. 당신은 아마도이 알고리즘이 가장 높은 배낭에 맞는 항목의 가치를 가진 해결책을 찾도록 고안되었다는 것을 알고 있습니다. 나는 그것이 최저 값을 가진 해결책을 찾고자한다. 여기

코드입니다 : 내가 몇 가지를 시도

var data= [ 
    {name: 'map',     weight: 9, value:150, pieces:1}, 
    {name: 'compass',    weight: 13, value: 35, pieces:1}, 
    {name: 'water',     weight:153, value:200, pieces:2}, 
    {name: 'sandwich',    weight: 50, value: 60, pieces:2}, 
    {name: 'glucose',    weight: 15, value: 60, pieces:2}, 
    {name: 'tin',     weight: 68, value: 45, pieces:3}, 
    {name: 'banana',     weight: 27, value: 60, pieces:3}, 
    {name: 'apple',     weight: 39, value: 40, pieces:3}, 
    {name: 'cheese',     weight: 23, value: 30, pieces:1}, 
    {name: 'beer',     weight: 52, value: 10, pieces:3}, 
    {name: 'suntan, cream',   weight: 11, value: 70, pieces:1}, 
    {name: 'camera',     weight: 32, value: 30, pieces:1}, 
    {name: 'T-shirt',    weight: 24, value: 15, pieces:2}, 
    {name: 'trousers',    weight: 48, value: 10, pieces:2}, 
    {name: 'umbrella',    weight: 73, value: 40, pieces:1}, 
    {name: 'waterproof, trousers', weight: 42, value: 70, pieces:1}, 
    {name: 'waterproof, overclothes',weight: 43, value: 75, pieces:1}, 
    {name: 'note-case',    weight: 22, value: 80, pieces:1}, 
    {name: 'sunglasses',    weight: 7, value: 20, pieces:1}, 
    {name: 'towel',     weight: 18, value: 12, pieces:2}, 
    {name: 'socks',     weight: 4, value: 50, pieces:1}, 
    {name: 'book',     weight: 30, value: 10, pieces:2} 
]; 

function findBestPack() { 
    var m= [[0]]; // maximum pack value found so far 
    var b= [[0]]; // best combination found so far 
    var opts= [0]; // item index for 0 of item 0 
    var P= [1]; // item encoding for 0 of item 0 
    var choose= 0; 
    for (var j= 0; j<data.length; j++) { 
     opts[j+1]= opts[j]+data[j].pieces; // item index for 0 of item j+1 
     P[j+1]= P[j]*(1+data[j].pieces); // item encoding for 0 of item j+1 
    } 
    for (var j= 0; j<opts[data.length]; j++) { 
     m[0][j+1]= b[0][j+1]= 0; // best values and combos for empty pack: nothing 
    } 
    for (var w=1; w<=400; w++) { 
     m[w]= [0]; 
     b[w]= [0]; 
     for (var j=0; j<data.length; j++) { 
      var N= data[j].pieces; // how many of these can we have? 
      var base= opts[j]; // what is the item index for 0 of these? 
      for (var n= 1; n<=N; n++) { 
       var W= n*data[j].weight; // how much do these items weigh? 
       var s= w>=W ?1 :0; // can we carry this many? 
       var v= s*n*data[j].value; // how much are they worth? 
       var I= base+n; // what is the item number for this many? 
       var wN= w-s*W; // how much other stuff can we be carrying? 
       var C= n*P[j] + b[wN][base]; // encoded combination 
       m[w][I]= Math.max(m[w][I-1], v+m[wN][base]); // best value 
       choose= b[w][I]= m[w][I]>m[w][I-1] ?C :b[w][I-1]; 
      } 
     } 
    } 
    var best= []; 
    for (var j= data.length-1; j>=0; j--) { 
     best[j]= Math.floor(choose/P[j]); 
     choose-= best[j]*P[j]; 
    } 

하지만 너희들이 나를 도울 수있는, 나를 위해 작동하지 않았다?

알고리즘은 400 개의 용량을 가진 컨테이너에 맞는 항목을 찾아서 400 개를 초과하지 않는 항목을 포함 할 수 있습니다. 또한 최상의 가치를 지닌 항목을 맞추려고 시도합니다. 예를 들어, 1 개의 항목이 10 개의 가중치와 5 개의 값을 갖는 알고리즘은 10 개의 가중치와 4 개의 값을 갖는 항목 대신이 항목을 취합니다. 알고리즘을 값으로 만들 때 알고리즘을 반전시켜 알고리즘이 5 대신 4 값으로 항목을 선택합니다.

Answer 1

일반적으로 가장 낮은 값에 대한 바닐라 배낭 문제에 대한 해결책은 간단합니다. 아무것도. 특정 체중 임계 값에 대해 가장 낮은 값을 말하는 경우 여기에 힌트가 있습니다. 모든 값을 무효화하십시오. 이 경우 가장 높은 값의 배낭이 가장 적은 음수입니다.