Question

Trong truyện cổ tích "Cây Khế" ta đã biết rằng chim thần chở người anh với một cái túi ba gang đến hòn đảo đầy vàng bạc châu báu. Người em băn khoăn không biết chọn đồ vật nào cho vào túi vì chỉ có một cái túi ba gang..

Giả sử rằng trên hòn đảo kia có N đồ vật khác nhau, đồ vật thứ i có giá trị là ai và có thể tích là bi. Cũng giả sử rằng cái túi mà người em mang đi chỉ có thể tích là M. Bạn hãy giúp người em chọn ra trong N đồ vật trên một số đồ vật sao cho tổng thể tích của các đồ vật được chọn không vượt quá M và tổng giá trị các đồ vật được chọn là lớn nhất.

Input: Cho trong file văn bản CAYKHE.INP

• Dòng đầu tiên ghi hai số N, M (N,M≤100)
• N dòng tiếp theo, dòng thứ i ghi hai số ai và bi lần lượt là giá trị và thể tích của đồ vật thứ i (ai, bi≤100)

Output: Ghi ra file văn bản CAYKHE.OUT

• Dòng đầu tiên ghi tổng giá trị lớn nhất có thể cho vào trong túi
• Dòng thứ hai ghi số hiệu các đồ vật được cho vào trong túi. Đầu tiên ghi K là số lượng đồ vật được chọn, tiếp theo là K số thể hiện số hiệu các đồ vật được chọn.

Ví dụ:

CAYKHE.INP	CAYKHE.OUT
5 10 20 3 19 1 30 7 24 3 15 6	63 3 1 2 4

Comments

đây là tin ý hả :)))

Answer 1

#include
using namespace std;
int main() {
    freopen("CAYKHE.INP","r",stdin);
    freopen("CAYKHE.OUT","w",stdout);
    int N, M;
    cin >> N >> M;
    vector vl(N + 1);
    vector vo(N + 1);
    for (int i = 1; i <= N; i++) {<br />         cin >> vl[i] >> vo[i];
    }
    vector > dp(N + 1, vector(M + 1, 0));
    for (int i = 1; i <= N; i++) {<br />         for (int j = 0; j <= M; j++) {<br />             if (vo[i] <= j) {<br />                 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vo[i]] + vl[i]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    int max_vl = dp[N][M];
    cout << max_vl << endl;<br />     vector s;
    int r = M;
    for (int i = N; i > 0 && max_vl > 0; i--) {
        if (max_vl != dp[i - 1][r]) {
            s.push_back(i);
            max_vl -= vl[i];
            r -= vo[i];
        }
    }
    cout << s.size();<br />     for (int i = s.size() - 1; i >= 0; i--) {
        cout << " " << s[i];<br />     }
    cout << endl;</p>

    return 0;
}