0-1背包【代码实现】

C

#include <stdio.h> #include <stdlib.h> typedef struct { char *name; int weight; int value; } item_t; item_t items[] = { {"map", 9, 150}, {"compass", 13, 35}, {"water", 153, 200}, {"sandwich", 50, 160}, {"glucose", 15, 60}, {"tin", 68, 45}, {"banana", 27, 60}, {"apple", 39, 40}, {"cheese", 23, 30}, {"beer", 52, 10}, {"suntan cream", 11, 70}, {"camera", 32, 30}, {"T-shirt", 24, 15}, {"trousers", 48, 10}, {"umbrella", 73, 40}, {"waterproof trousers", 42, 70}, {"waterproof overclothes", 43, 75}, {"note-case", 22, 80}, {"sunglasses", 7, 20}, {"towel", 18, 12}, {"socks", 4, 50}, {"book", 30, 10}, }; int *knapsack (item_t *items, int n, int w) { int i, j, a, b, *mm, **m, *s; mm = calloc((n + 1) * (w + 1), sizeof (int)); m = malloc((n + 1) * sizeof (int *)); m[0] = mm; for (i = 1; i <= n; i++) { m[i] = &mm[i * (w + 1)]; for (j = 0; j <= w; j++) { if (items[i - 1].weight > j) { m[i][j] = m[i - 1][j]; } else { a = m[i - 1][j]; b = m[i - 1][j - items[i - 1].weight] + items[i - 1].value; m[i][j] = a > b ? a : b; } } } s = calloc(n, sizeof (int)); for (i = n, j = w; i > 0; i--) { if (m[i][j] > m[i - 1][j]) { s[i - 1] = 1; j -= items[i - 1].weight; } } free(mm); free(m); return s; } int main () { int i, n, tw = 0, tv = 0, *s; n = sizeof (items) / sizeof (item_t); s = knapsack(items, n, 400); for (i = 0; i < n; i++) { if (s[i]) { printf("%-22s ] ]\n", items[i].name, items[i].weight, items[i].value); tw += items[i].weight; tv += items[i].value; } } printf("%-22s ] ]\n", "totals:", tw, tv); return 0; }

输出

map 9 150 compass 13 35 water 153 200 sandwich 50 160 glucose 15 60 banana 27 60 suntan cream 11 70 waterproof trousers 42 70 waterproof overclothes 43 75 note-case 22 80 sunglasses 7 20 socks 4 50 totals: 396 1030

C++

#include <vector> #include <string> #include <iostream> #include <boost/tuple/tuple.hpp> #include <set> int findBestPack( const std::vector<boost::tuple<std::string , int , int> > & , std::set<int> & , const int ) ; int main( ) { std::vector<boost::tuple<std::string , int , int> > items ; //===========fill the vector with data==================== items.push_back( boost::make_tuple( "" , 0 , 0 ) ) ; items.push_back( boost::make_tuple( "map" , 9 , 150 ) ) ; items.push_back( boost::make_tuple( "compass" , 13 , 35 ) ) ; items.push_back( boost::make_tuple( "water" , 153 , 200 ) ) ; items.push_back( boost::make_tuple( "sandwich", 50 , 160 ) ) ; items.push_back( boost::make_tuple( "glucose" , 15 , 60 ) ) ; items.push_back( boost::make_tuple( "tin", 68 , 45 ) ) ; items.push_back( boost::make_tuple( "banana", 27 , 60 ) ) ; items.push_back( boost::make_tuple( "apple" , 39 , 40 ) ) ; items.push_back( boost::make_tuple( "cheese" , 23 , 30 ) ) ; items.push_back( boost::make_tuple( "beer" , 52 , 10 ) ) ; items.push_back( boost::make_tuple( "suntan creme" , 11 , 70 ) ) ; items.push_back( boost::make_tuple( "camera" , 32 , 30 ) ) ; items.push_back( boost::make_tuple( "T-shirt" , 24 , 15 ) ) ; items.push_back( boost::make_tuple( "trousers" , 48 , 10 ) ) ; items.push_back( boost::make_tuple( "umbrella" , 73 , 40 ) ) ; items.push_back( boost::make_tuple( "waterproof trousers" , 42 , 70 ) ) ; items.push_back( boost::make_tuple( "waterproof overclothes" , 43 , 75 ) ) ; items.push_back( boost::make_tuple( "note-case" , 22 , 80 ) ) ; items.push_back( boost::make_tuple( "sunglasses" , 7 , 20 ) ) ; items.push_back( boost::make_tuple( "towel" , 18 , 12 ) ) ; items.push_back( boost::make_tuple( "socks" , 4 , 50 ) ) ; items.push_back( boost::make_tuple( "book" , 30 , 10 ) ) ; const int maximumWeight = 400 ; std::set<int> bestItems ; //these items will make up the optimal value int bestValue = findBestPack( items , bestItems , maximumWeight ) ; std::cout << "The best value that can be packed in the given knapsack is " << bestValue << " !\n" ; int totalweight = 0 ; std::cout << "The following items should be packed in the knapsack:\n" ; for ( std::set<int>::const_iterator si = bestItems.begin( ) ; si != bestItems.end( ) ; si++ ) { std::cout << (items.begin( ) + *si)->get<0>( ) << "\n" ; totalweight += (items.begin( ) + *si)->get<1>( ) ; } std::cout << "The total weight of all items is " << totalweight << " !\n" ; return 0 ; } int findBestPack( const std::vector<boost::tuple<std::string , int , int> > & items ,std::set<int> & bestItems , const int weightlimit ) { //dynamic programming approach sacrificing storage space for execution //time , creating a table of optimal values for every weight and a //second table of sets with the items collected so far in the knapsack //the best value is in the bottom right corner of the values table, //the set of items in the bottom right corner of the sets' table. const int n = items.size( ) ; int bestValues [ n ][ weightlimit ] ; std::set<int> solutionSets[ n ][ weightlimit ] ; std::set<int> emptyset ; for ( int i = 0 ; i < n ; i++ ) { for ( int j = 0 ; j < weightlimit ; j++ ) { bestValues[ i ][ j ] = 0 ; solutionSets[ i ][ j ] = emptyset ; } } for ( int i = 0 ; i < n ; i++ ) { for ( int weight = 0 ; weight < weightlimit ; weight++ ) { if ( i == 0 ) bestValues[ i ][ weight ] = 0 ; else { int itemweight = (items.begin( ) + i)->get<1>( ) ; if ( weight < itemweight ) { bestValues[ i ][ weight ] = bestValues[ i - 1 ][ weight ] ; solutionSets[ i ][ weight ] = solutionSets[ i - 1 ][ weight ] ; } else { // weight >= itemweight if ( bestValues[ i - 1 ][ weight - itemweight ] + (items.begin( ) + i)->get<2>( ) > bestValues[ i - 1 ][ weight ] ) { bestValues[ i ][ weight ] = bestValues[ i - 1 ][ weight - itemweight ] + (items.begin( ) + i)->get<2>( ) ; solutionSets[ i ][ weight ] = solutionSets[ i - 1 ][ weight - itemweight ] ; solutionSets[ i ][ weight ].insert( i ) ; } else { bestValues[ i ][ weight ] = bestValues[ i - 1 ][ weight ] ; solutionSets[ i ][ weight ] = solutionSets[ i - 1 ][ weight ] ; } } } } } bestItems.swap( solutionSets[ n - 1][ weightlimit - 1 ] ) ; return bestValues[ n - 1 ][ weightlimit - 1 ] ; }

输出

The best value that can be packed in the given knapsack is 1030 ! The following items should be packed in the knapsack: map compass water sandwich glucose banana suntan creme waterproof trousers waterproof overclothes note-case sunglasses socks The total weight of all items is 396 !

C#

using System; using System.Collections.Generic; namespace Tests_With_Framework_4 { class Bag : IEnumerable<Bag.Item> { List<Item> items; const int MaxWeightAllowed = 400; public Bag() { items = new List<Item>(); } void AddItem(Item i) { if ((TotalWeight + i.Weight) <= MaxWeightAllowed) items.Add(i); } public void Calculate(List<Item> items) { foreach (Item i in Sorte(items)) { AddItem(i); } } List<Item> Sorte(List<Item> inputItems) { List<Item> choosenItems = new List<Item>(); for (int i = 0; i < inputItems.Count; i++) { int j = -1; if (i == 0) { choosenItems.Add(inputItems[i]); } if (i > 0) { if (!RecursiveF(inputItems, choosenItems, i, choosenItems.Count - 1, false, ref j)) { choosenItems.Add(inputItems[i]); } } } return choosenItems; } bool RecursiveF(List<Item> knapsackItems, List<Item> choosenItems, int i, int lastBound, bool dec, ref int indxToAdd) { if (!(lastBound < 0)) { if ( knapsackItems[i].ResultWV < choosenItems[lastBound].ResultWV ) { indxToAdd = lastBound; } return RecursiveF(knapsackItems, choosenItems, i, lastBound - 1, true, ref indxToAdd); } if (indxToAdd > -1) { choosenItems.Insert(indxToAdd, knapsackItems[i]); return true; } return false; } #region IEnumerable<Item> Members IEnumerator<Item> IEnumerable<Item>.GetEnumerator() { foreach (Item i in items) yield return i; } #endregion #region IEnumerable Members System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return items.GetEnumerator(); } #endregion public int TotalWeight { get { var sum = 0; foreach (Item i in this) { sum += i.Weight; } return sum; } } public class Item { public string Name { get; set; } public int Weight { get; set; } public int Value { get; set; } public int ResultWV { get { return Weight-Value; } } public override string ToString() { return "Name : " + Name + " Wieght : " + Weight + " Value : " + Value + " ResultWV : " + ResultWV; } } } class Program { static void Main(string[] args) {List<Bag.Item> knapsackItems = new List<Bag.Item>(); knapsackItems.Add(new Bag.Item() { Name = "Map", Weight = 9, Value = 150 }); knapsackItems.Add(new Bag.Item() { Name = "Water", Weight = 153, Value = 200 }); knapsackItems.Add(new Bag.Item() { Name = "Compass", Weight = 13, Value = 35 }); knapsackItems.Add(new Bag.Item() { Name = "Sandwitch", Weight = 50, Value = 160 }); knapsackItems.Add(new Bag.Item() { Name = "Glucose", Weight = 15, Value = 60 }); knapsackItems.Add(new Bag.Item() { Name = "Tin", Weight = 68, Value = 45 }); knapsackItems.Add(new Bag.Item() { Name = "Banana", Weight = 27, Value = 60 }); knapsackItems.Add(new Bag.Item() { Name = "Apple", Weight = 39, Value = 40 }); knapsackItems.Add(new Bag.Item() { Name = "Cheese", Weight = 23, Value = 30 }); knapsackItems.Add(new Bag.Item() { Name = "Beer", Weight = 52, Value = 10 }); knapsackItems.Add(new Bag.Item() { Name = "Suntan Cream", Weight = 11, Value = 70 }); knapsackItems.Add(new Bag.Item() { Name = "Camera", Weight = 32, Value = 30 }); knapsackItems.Add(new Bag.Item() { Name = "T-shirt", Weight = 24, Value = 15 }); knapsackItems.Add(new Bag.Item() { Name = "Trousers", Weight = 48, Value = 10 }); knapsackItems.Add(new Bag.Item() { Name = "Umbrella", Weight = 73, Value = 40 }); knapsackItems.Add(new Bag.Item() { Name = "WaterProof Trousers", Weight = 42, Value = 70 }); knapsackItems.Add(new Bag.Item() { Name = "Note-Case", Weight = 22, Value = 80 }); knapsackItems.Add(new Bag.Item() { Name = "Sunglasses", Weight = 7, Value = 20 }); knapsackItems.Add(new Bag.Item() { Name = "Towel", Weight = 18, Value = 12 }); knapsackItems.Add(new Bag.Item() { Name = "Socks", Weight = 4, Value = 50 }); knapsackItems.Add(new Bag.Item() { Name = "Book", Weight = 30, Value = 10 }); knapsackItems.Add(new Bag.Item() { Name = "waterproof overclothes ", Weight = 43, Value = 75 }); Bag b = new Bag(); b.Calculate(knapsackItems); b.All(x => { Console.WriteLine(x); return true; }); Console.WriteLine(b.Sum(x => x.Weight)); Console.ReadKey(); } } }

Dart

List solveKnapsack(items, maxWeight) { int MIN_VALUE=-100; int N = items.length; // number of items int W = maxWeight; // maximum weight of knapsack List profit = new List(N+1); List weight = new List(N+1); // generate random instance, items 1..N for(int n = 1; n<=N; n++) { profit[n] = items[n-1][2]; weight[n] = items[n-1][1]; } // opt[n][w] = max profit of packing items 1..n with weight limit w // sol[n][w] = does opt solution to pack items 1..n with weight limit w include item n? List<List<int>> opt = new List<List<int>>(N+1); for (int i=0; i<N+1; i++) { opt[i] = new List<int>(W+1); for(int j=0; j<W+1; j++) { opt[i][j] = MIN_VALUE; } } List<List<bool>> sol = new List<List<bool>>(N+1); for (int i=0; i<N+1; i++) { sol[i] = new List<bool>(W+1); for(int j=0; j<W+1; j++) { sol[i][j] = false; } } for(int n=1; n<=N; n++) { for (int w=1; w <= W; w++) { // don't take item n int option1 = opt[n-1][w]; // take item n int option2 = MIN_VALUE; if (weight[n] <= w) { option2 = profit[n] + opt[n-1][w - weight[n]]; } // select better of two options opt[n][w] = Math.max(option1, option2); sol[n][w] = (option2 > option1); } } // determine which items to take List<List> packItems = new List<List>(); List<bool> take = new List(N+1); for (int n = N, w = W; n > 0; n--) { if (sol[n][w]) { take[n] = true; w = w - weight[n]; packItems.add(items[n-1]); } else { take[n] = false; } } return packItems; } main() { List knapsackItems = []; knapsackItems.add(["map", 9, 150]); knapsackItems.add(["compass", 13, 35]); knapsackItems.add(["water", 153, 200]); knapsackItems.add(["sandwich", 50, 160]); knapsackItems.add(["glucose", 15, 60]); knapsackItems.add(["tin", 68, 45]); knapsackItems.add(["banana", 27, 60]); knapsackItems.add(["apple", 39, 40]); knapsackItems.add(["cheese", 23, 30]); knapsackItems.add(["beer", 52, 10]); knapsackItems.add(["suntan cream", 11, 70]); knapsackItems.add(["camera", 32, 30]); knapsackItems.add(["t-shirt", 24, 15]); knapsackItems.add(["trousers", 48, 10]); knapsackItems.add(["umbrella", 73, 40]); knapsackItems.add(["waterproof trousers", 42, 70]); knapsackItems.add(["waterproof overclothes", 43, 75]); knapsackItems.add(["note-case", 22, 80]); knapsackItems.add(["sunglasses", 7, 20]); knapsackItems.add(["towel", 18, 12]); knapsackItems.add(["socks", 4, 50]); knapsackItems.add(["book", 30, 10]); int maxWeight = 400; Stopwatch sw = new Stopwatch.start(); List p = solveKnapsack(knapsackItems, maxWeight); sw.stop(); int totalWeight = 0; int totalValue = 0; print(["item","profit","weight"]); p.forEach((var i) { print("${i}"); totalWeight+=i[1]; totalValue+=i[2]; }); print("Total Value = ${totalValue}"); print("Total Weight = ${totalWeight}"); print("Elapsed Time = ${sw.elapsedInMs()}ms"); }

Go

package main import "fmt" type item struct { string w, v int } var wants = []item{ {"map", 9, 150}, {"compass", 13, 35}, {"water", 153, 200}, {"sandwich", 50, 160}, {"glucose", 15, 60}, {"tin", 68, 45}, {"banana", 27, 60}, {"apple", 39, 40}, {"cheese", 23, 30}, {"beer", 52, 10}, {"suntan cream", 11, 70}, {"camera", 32, 30}, {"T-shirt", 24, 15}, {"trousers", 48, 10}, {"umbrella", 73, 40}, {"waterproof trousers", 42, 70}, {"waterproof overclothes", 43, 75}, {"note-case", 22, 80}, {"sunglasses", 7, 20}, {"towel", 18, 12}, {"socks", 4, 50}, {"book", 30, 10}, } const maxWt = 400 func main() { items, w, v := m(len(wants)-1, maxWt) fmt.Println(items) fmt.Println("weight:", w) fmt.Println("value:", v) } func m(i, w int) ([]string, int, int) { if i < 0 || w == 0 { return nil, 0, 0 } else if wants[i].w > w { return m(i-1, w) } i0, w0, v0 := m(i-1, w) i1, w1, v1 := m(i-1, w-wants[i].w) v1 += wants[i].v if v1 > v0 { return append(i1, wants[i].string), w1 + wants[i].w, v1 } return i0, w0, v0 }

Java

package com.pro.alg.test; import com.pro.alg.ZeroOneKnapsack; import com.pro.obj.Item; import java.util.*; import java.text.*; public class ZeroOneKnapsackForTourists { public ZeroOneKnapsackForTourists() { ZeroOneKnapsack zok = new ZeroOneKnapsack(400); // 400 dkg = 400 dag = 4 kg // making the list of items that you want to bring zok.add("map", 9, 150); zok.add("compass", 13, 35); zok.add("water", 153, 200); zok.add("sandwich", 50, 160); zok.add("glucose", 15, 60); zok.add("tin", 68, 45); zok.add("banana", 27, 60); zok.add("apple", 39, 40); zok.add("cheese", 23, 30); zok.add("beer", 52, 10); zok.add("suntan cream", 11, 70); zok.add("camera", 32, 30); zok.add("t-shirt", 24, 15); zok.add("trousers", 48, 10); zok.add("umbrella", 73, 40); zok.add("waterproof trousers", 42, 70); zok.add("waterproof overclothes", 43, 75); zok.add("note-case", 22, 80); zok.add("sunglasses", 7, 20); zok.add("towel", 18, 12); zok.add("socks", 4, 50); zok.add("book", 30, 10); // calculate the solution: List<Item> itemList = zok.calcSolution(); // write out the solution in the standard output if (zok.isCalculated()) { NumberFormat nf = NumberFormat.getInstance(); System.out.println( "Maximal weight = " + nf.format(zok.getMaxWeight() / 100.0) + " kg" ); System.out.println( "Total weight of solution = " + nf.format(zok.getSolutionWeight() / 100.0) + " kg" ); System.out.println( "Total value = " + zok.getProfit() ); System.out.println(); System.out.println( "You can carry the following materials " + "in the knapsack:" ); for (Item item : itemList) { if (item.getInKnapsack() == 1) { System.out.format( "%1$-23s %2$-3s %3$-5s %4$-15s \n", item.getName(), item.getWeight(), "dag ", "(value = " + item.getValue() + ")" ); } } } else { System.out.println( "The problem is not solved. " + "Maybe you gave wrong data." ); } } public static void main(String[] args) { new ZeroOneKnapsackForTourists(); } } // class package com.pro.alg; import com.pro.obj.Item; import java.util.*; public class ZeroOneKnapsack { protected List<Item> itemList = new ArrayList<Item>(); protected int maxWeight = 0; protected int solutionWeight = 0; protected int profit = 0; protected boolean calculated = false; public ZeroOneKnapsack() {} public ZeroOneKnapsack(int _maxWeight) { setMaxWeight(_maxWeight); } public ZeroOneKnapsack(List<Item> _itemList) { setItemList(_itemList); } public ZeroOneKnapsack(List<Item> _itemList, int _maxWeight) { setItemList(_itemList); setMaxWeight(_maxWeight); } // calculte the solution of 0-1 knapsack problem with dynamic method: public List<Item> calcSolution() { int n = itemList.size(); setInitialStateForCalculation(); if (n > 0 && maxWeight > 0) { List< List<Integer> > c = new ArrayList< List<Integer> >(); List<Integer> curr = new ArrayList<Integer>(); c.add(curr); for (int j = 0; j <= maxWeight; j++) curr.add(0); for (int i = 1; i <= n; i++) { List<Integer> prev = curr; c.add(curr = new ArrayList<Integer>()); for (int j = 0; j <= maxWeight; j++) { if (j > 0) { int wH = itemList.get(i-1).getWeight(); curr.add( (wH > j) ? prev.get(j) : Math.max( prev.get(j), itemList.get(i-1).getValue() + prev.get(j-wH) ) ); } else { curr.add(0); } } // for (j...) } // for (i...) profit = curr.get(maxWeight); for (int i = n, j = maxWeight; i > 0 && j >= 0; i--) { int tempI = c.get(i).get(j); int tempI_1 = c.get(i-1).get(j); if ( (i == 0 && tempI > 0) || (i > 0 && tempI != tempI_1) ) { Item iH = itemList.get(i-1); int wH = iH.getWeight(); iH.setInKnapsack(1); j -= wH; solutionWeight += wH; } } // for() calculated = true; } // if() return itemList; } // add an item to the item list public void add(String name, int weight, int value) { if (name.equals("")) name = "" + (itemList.size() + 1); itemList.add(new Item(name, weight, value)); setInitialStateForCalculation(); } // add an item to the item list public void add(int weight, int value) { add("", weight, value); // the name will be "itemList.size() + 1"! } // remove an item from the item list public void remove(String name) { for (Iterator<Item> it = itemList.iterator(); it.hasNext(); ) { if (name.equals(it.next().getName())) { it.remove(); } } setInitialStateForCalculation(); } // remove all items from the item list public void removeAllItems() { itemList.clear(); setInitialStateForCalculation(); } public int getProfit() { if (!calculated) calcSolution(); return profit; } public int getSolutionWeight() {return solutionWeight;} public boolean isCalculated() {return calculated;} public int getMaxWeight() {return maxWeight;} public void setMaxWeight(int _maxWeight) { maxWeight = Math.max(_maxWeight, 0); } public void setItemList(List<Item> _itemList) { if (_itemList != null) { itemList = _itemList; for (Item item : _itemList) { item.checkMembers(); } } } // set the member with name "inKnapsack" by all items: private void setInKnapsackByAll(int inKnapsack) { for (Item item : itemList) if (inKnapsack > 0) item.setInKnapsack(1); else item.setInKnapsack(0); } // set the data members of class in the state of starting the calculation: protected void setInitialStateForCalculation() { setInKnapsackByAll(0); calculated = false; profit = 0; solutionWeight = 0; } } // class package com.pro.obj; public class Item { protected String name = ""; protected int weight = 0; protected int value = 0; protected int bounding = 1; // the maximal limit of item's pieces protected int inKnapsack = 0; // the pieces of item in solution public Item() {} public Item(Item item) { setName(item.name); setWeight(item.weight); setValue(item.value); setBounding(item.bounding); } public Item(int _weight, int _value) { setWeight(_weight); setValue(_value); } public Item(int _weight, int _value, int _bounding) { setWeight(_weight); setValue(_value); setBounding(_bounding); } public Item(String _name, int _weight, int _value) { setName(_name); setWeight(_weight); setValue(_value); } public Item(String _name, int _weight, int _value, int _bounding) { setName(_name); setWeight(_weight); setValue(_value); setBounding(_bounding); } public void setName(String _name) {name = _name;} public void setWeight(int _weight) {weight = Math.max(_weight, 0);} public void setValue(int _value) {value = Math.max(_value, 0);} public void setInKnapsack(int _inKnapsack) { inKnapsack = Math.min(getBounding(), Math.max(_inKnapsack, 0)); } public void setBounding(int _bounding) { bounding = Math.max(_bounding, 0); if (bounding == 0) inKnapsack = 0; } public void checkMembers() { setWeight(weight); setValue(value); setBounding(bounding); setInKnapsack(inKnapsack); } public String getName() {return name;} public int getWeight() {return weight;} public int getValue() {return value;} public int getInKnapsack() {return inKnapsack;} public int getBounding() {return bounding;} } // class

输出

Maximal weight = 4 kg Total weight of solution = 3,96 kg Total value = 1030 You can carry te following materials in the knapsack: map 9 dag (value = 150) compass 13 dag (value = 35) water 153 dag (value = 200) sandwich 50 dag (value = 160) glucose 15 dag (value = 60) banana 27 dag (value = 60) suntan cream 11 dag (value = 70) waterproof trousers 42 dag (value = 70) waterproof overclothes 43 dag (value = 75) note-case 22 dag (value = 80) sunglasses 7 dag (value = 20) socks 4 dag (value = 50)

Javascript

/*global portviz:false, _:false */ /* * 0-1 knapsack solution, recursive, memoized, approximate. * * credits: * * the Go implementation here: * http://rosettacode.org/mw/index.php?title=Knapsack_problem/0-1 * * approximation details here: * http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf */ portviz.knapsack = {}; (function() { this.combiner = function(items, weightfn, valuefn) { // approximation guarantees result >= (1-e) * optimal var _epsilon = 0.01; var _p = _.max(_.map(items,valuefn)); var _k = _epsilon * _p / items.length; var _memo = (function(){ var _mem = {}; var _key = function(i, w) { return i + '::' + w; }; return { get: function(i, w) { return _mem[_key(i,w)]; }, put: function(i, w, r) { _mem[_key(i,w)]=r; return r; } }; })(); var _m = function(i, w) { i = Math.round(i); w = Math.round(w); if (i < 0 || w === 0) { // empty base case return {items: [], totalWeight: 0, totalValue: 0}; } var mm = _memo.get(i,w); if (!_.isUndefined(mm)) { return mm; } var item = items[i]; if (weightfn(item) > w) { //item does not fit, try the next item return _memo.put(i, w, _m(i-1, w)); } // this item could fit. // are we better off excluding it? var excluded = _m(i-1, w); // or including it? var included = _m(i-1, w - weightfn(item)); if (included.totalValue + Math.floor(valuefn(item)/_k) > excluded.totalValue) { // better off including it // make a copy of the list var i1 = included.items.slice(); i1.push(item); return _memo.put(i, w, {items: i1, totalWeight: included.totalWeight + weightfn(item), totalValue: included.totalValue + Math.floor(valuefn(item)/_k)}); } //better off excluding it return _memo.put(i,w, excluded); }; return { /* one point */ one: function(maxweight) { var scaled = _m(items.length - 1, maxweight); return { items: scaled.items, totalWeight: scaled.totalWeight, totalValue: scaled.totalValue * _k }; }, /* the entire EF */ ef: function(maxweight, step) { return _.map(_.range(0, maxweight+1, step), function(weight) { var scaled = _m(items.length - 1, weight); return { items: scaled.items, totalWeight: scaled.totalWeight, totalValue: scaled.totalValue * _k }; }); } }; }; }).apply(portviz.knapsack); /*global portviz:false, _:false */ /* * after rosettacode.org/mw/index.php?title=Knapsack_problem/0-1 */ var allwants = [ {name:"map", weight:9, value: 150}, {name:"compass", weight:13, value: 35}, {name:"water", weight:153, value: 200}, {name:"sandwich", weight: 50, value: 160}, {name:"glucose", weight:15, value: 60}, {name:"tin", weight:68, value: 45}, {name:"banana", weight:27, value: 60}, {name:"apple", weight:39, value: 40}, {name:"cheese", weight:23, value: 30}, {name:"beer", weight:52, value: 10}, {name:"suntan cream", weight:11, value: 70}, {name:"camera", weight:32, value: 30}, {name:"T-shirt", weight:24, value: 15}, {name:"trousers", weight:48, value: 10}, {name:"umbrella", weight:73, value: 40}, {name:"waterproof trousers", weight:42, value: 70}, {name:"waterproof overclothes", weight:43, value: 75}, {name:"note-case", weight:22, value: 80}, {name:"sunglasses", weight:7, value: 20}, {name:"towel", weight:18, value: 12}, {name:"socks", weight:4, value: 50}, {name:"book", weight:30, value: 10} ]; var near = function(actual, expected, tolerance) { if (expected === 0 && actual === 0) return true; if (expected === 0) { return Math.abs(expected - actual) / actual < tolerance; } return Math.abs(expected - actual) / expected < tolerance; }; test("one knapsack", function() { var combiner = portviz.knapsack.combiner(allwants, function(x){return x.weight;}, function(x){return x.value;}); var oneport = combiner.one(400); ok(near(oneport.totalValue, 1030, 0.01), "correct total value"); ok(near(oneport.totalValue, 1030, 0.01), "correct total value"); equal(oneport.totalWeight, 396, "correct total weight"); }); test("frontier", function() { var combiner = portviz.knapsack.combiner(allwants, function(x){return x.weight;}, function(x){return x.value;}); var ef = combiner.ef(400, 1); equal(ef.length, 401, "401 because it includes the endpoints"); ef = combiner.ef(400, 40); equal(ef.length, 11, "11 because it includes the endpoints"); var expectedTotalValue = [ 0, 330, 445, 590, 685, 755, 810, 860, 902, 960, 1030 ] ; _.each(ef, function(element, index) { // 15% error! bleah! ok(near(element.totalValue, expectedTotalValue[index], 0.15), 'actual ' + element.totalValue + ' expected ' + expectedTotalValue[index]); }); deepEqual(_.pluck(ef, 'totalWeight'), [ 0, 39, 74, 118, 158, 200, 236, 266, 316, 354, 396 ]); deepEqual(_.map(ef, function(x){return x.items.length;}), [ 0, 4, 6, 7, 9, 10, 10, 12, 14, 11, 12 ]); });