UESTC 1691 这是一道比CCCC简单题经典的中档题 多重背包

这是一道比CCCC简单题经典的中档题 多重背包

Source

2017 UESTC Training for Dynamic Programming

UESTC 1691 这是一道比CCCC简单题经典的中档题

My Solution

多重背包
转化成0-1背包来跑。
for(i = 1; i <= n; i++){
for(k = 0; k <= c[i]; k++){
for(j = w; j >= 0; j--){
if(j - k*need[i] >= 0) dp[i][j] = max(dp[i][j], dp[i-1][j-k*need[i]] + k*value[i]);
else break;
}
}
for(j = 0; j <= w; j++){
if(j) dp[i][j] = max(dp[i][j], dp[i][j-1]);
}
}
时间复杂度 O(n*sigma(ci))
空间复杂度 O(n^w)

#include 
#include 

using namespace std;
typedef long long LL;
const int MAXN = 1e2 + 8, MAXM = 5e4 + 8;

int need[MAXN], value[MAXN], c[MAXN], dp[MAXN][MAXM];

template 
inline void cinn(T &ret)
{
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    ret=c-'0';
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); } int main() { #ifdef LOCAL freopen("m.txt", "r", stdin); //freopen("m.out", "w", stdout); #endif // LOCAL //ios::sync_with_stdio(false); cin.tie(0); int n, w, i, j, k; //cin >> n >> w;
    //scanf("%d%d", &n, &w);
    cinn(n); cinn(w);
    for(i = 1; i <= n; i++){ //cin >> need[i] >> value[i];
        //scanf("%d%d%d", &need[i], &value[i], &c[i]);
        cinn(need[i]); cinn(value[i]); cinn(c[i]);
    }
    for(i = 1; i <= n; i++){
        for(k = 0; k <= c[i]; k++){ for(j = w; j >= 0; j--){
                if(j - k*need[i] >= 0) dp[i][j] = max(dp[i][j], dp[i-1][j-k*need[i]] + k*value[i]);
                else break;
            }
        }
        for(j = 0; j <= w; j++){
            if(j) dp[i][j] = max(dp[i][j], dp[i][j-1]);
        }
    }
    //cout << dp[n-1][w] << endl;
    printf("%dn", dp[n][w]);
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx