Back
Cai_Tui.cpp
Save
// Cai_Tui.cpp #include <bits/stdc++.h> using namespace std; struct GoiHang { int w; //trong luong int v; //gia tri }; GoiHang gh[] = { {0, 0}, {1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}, }; int n = 6, m = 10; int F[7][11]; void CaiTui() { for (int j = 0; j <= m; j++) F[0][j] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { F[i][j] = F[i - 1][j]; int temp = F[i - 1][j - gh[i].w] + gh[i].v; if (gh[i].w <= j && F[i][j] < temp) F[i][j] = temp; } } } void TruyVet() { cout << "Gia tri lon nhat la: " << F[n][m] << endl; int i = n; int j = m; cout << "Goi\tKhoi luong\tGia tri" << endl; while (i != 0) { if (F[i][j] != F[i - 1][j]) { cout << i << "\t" << gh[i].w << "\t\t" << gh[i].v << endl;; j = j - gh[i].w; } i--; } } int main() { CaiTui(); TruyVet(); return 0; }