Метод укладання наплічника

[Yola]

Було нема чого робити, вирішив втілити "метод укладання наплічника" за допомогою динамічного програмування:

Код: [Вибрати]

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

struct Item {
      int weight;
      int profit;
};
typedef vector<Item> Items;

int main() {
//      Items items = {{1, 1}, {2, 3}, {3, 4}, {5, 7}, {7, 10}, {9, 12}};
      Items items = {{5, 10}, {4, 40}, {6, 30}, {3, 50}};
      int cap = 10;
      
      vector<vector<int> > t(cap + 1, vector<int>(items.size() + 1, 0));
      
      for (int j = 1; j <= items.size(); j++) {
            for (int i = 1; i <= cap; i++) {
                  int t1 = t[i][j-1];
                  Item& item = items[j-1];
                  int w = i - item.weight;
                  int t2 = w >= 0 ? item.profit + t[w][j-1] : 0;
                  t[i][j] =  t1 > t2 ? t1 : t2;
                  cout << setw(5) << setfill('.') << t[i][j];
            }
            cout << endl;
      }
      
      cout << t[cap][items.size()] << endl;

      return 0;
}

Маємо:
....0....0....0....0...10...10...10...10...10...10
....0....0....0...40...40...40...40...40...50...50
....0....0....0...40...40...40...40...40...50...70
....0....0...50...50...50...50...90...90...90...90
90

http://uk.wikipedia.org/wiki/Задача_пакування_рюкзака