#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;}
