louisfghbvc的部落格

題目連結:   https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=30013

題目大意: 每個人在有負重情況下，可以搬走的最高成本。

思路:  就背包問題，每個重量，都可以放這個或不放商品，計算成本最大。先建表，建完之後只要將總和紀錄就可。

由後往前，因為01背包。壓成1維才不會覆蓋原先的數值，若是2維dp可以不用考慮從後往前。

感覺題目都跟前面的一樣，而且中文題其實看很快。

dp[j] = dp[j] or dp[j - wight[i]] + cost[i]

代碼:  

#include <bits/stdc++.h>
#define N 1005
using namespace std;

int cost[N], weight[N], dp[N];
int main()
{
    int t, n, g, x;
    cin >> t;
    while(t--){
        memset(dp, 0, sizeof dp);
        cin >> n;
        for(int i = 0; i < n; i++){
            cin >> cost[i] >> weight[i];
        }
        for(int i = 0; i < n; ++i){
            for(int j = 30; j >= weight[i]; --j){
                dp[j] = max(dp[j], dp[j-weight[i]]+cost[i]);
            }
        }
        cin >> g;
        int sum = 0;
        while(g-- && cin >> x){
            sum += dp[x];
        }
        cout << sum << endl;
    }
    return 0;
}