Untitled

 
 ​#​include​ ​<​iostream​> 
 ​#​include​ ​<​vector​> 
 ​using​ ​namespace​ ​std​; 
 ​int​ n,b; 
 ​vector<​int​> a, c; ​//​ trọng lượng và giá trị sử  dụng của vật 
 ​int​ bk; ​//​ trọng lượng còn lại của túi 
 ​int​ fk; ​//​ giá trị hiện tại của túi 
 ​int​ fopt = ​0​; ​//​ giá trị tốt nhất của túi hiện có 
 ​int​ x[​31​]; ​//​ x[i] = 1 nếu đồ vật được chọn, =0 nếu ko được chọn 
 ​void​ ​input​() { 
 ​    cin >> n >> b; 
 ​    a.​push_back​(​0​); 
 ​    c.​push_back​(​0​); 
 ​    ​for​(​int​ i = ​0​; i < n; i++) { 
 ​        ​int​ weight, use; 
 ​        cin >> weight >> use; 
 ​        a.​push_back​(weight); 
 ​        c.​push_back​(use); 
 ​    } 
 ​    bk = b; 
 ​    fk = ​0​; 
 ​    fopt = fk; 
 ​} 
 ​void​ ​solve​(​int​ i) { 
 ​    ​int​ j,t; 
 ​    ​if​(bk >= a[i]) { ​//​nếu trọng lượng hiện tại >= trọng lượng của vật 
 ​        t = ​1​; ​//​ ok 
 ​    } 
 ​    ​else​ { 
 ​        t = ​0​; ​//​ cút 
 ​    } 
 ​    ​for​(j = t; j >= ​0​; j--) { 
 ​        x[i] = j; 
 ​        bk -= a[i]*x[i]; 
 ​        fk += c[i]*x[i]; 
 ​        ​if​(i==n) { 
 ​            ​if​(fk > fopt) { 
 ​                fopt = fk; 
 ​            } 
 ​        } 
 ​        ​else​ { 
 ​            ​solve​(i+​1​); 
 ​        } 
 ​        bk += a[i]*x[i]; 
 ​        fk -= c[i]*x[i]; 
 ​    } 
  
 ​} 
 ​int​ ​main​() { 
 ​    ​input​(); 
 ​    ​solve​(​1​); 
 ​    cout << fopt; 
 ​}