UESTC 1606 难喝的饮料 0-1背包+完全背包

难喝的饮料 0-1背包+完全背包

Source

2017 UESTC Training for Dynamic Programming

UESTC 1606 难喝的饮料

My Solution

0-1背包+完全背包
通过递推顺序，第一维可以直接省略
for(i = 1; i <= n; i++){
if(c[i]){//0-1背包
for(j = w; j >= 0; j--){
if(j - need[i] >= 0) dp[j] = max(dp[j], dp[j-need[i]] + value[i]);
else break;
}
}
else{//完全背包
for(j = 0; j <= w; j++){
if(j - need[i] >= 0) dp[j] = max(dp[j], dp[j-need[i]] + value[i]);
}
}
}
时间复杂度 O(n*k)
空间复杂度 O(k)

#include 
#include 

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

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

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("d.txt", "r", stdin); //freopen("d.out", "w", stdout); #endif // LOCAL //ios::sync_with_stdio(false); cin.tie(0); int n, w, t, i, j, k; //cin >> n >> w;
    //scanf("%d%d", &n, &w);
    cinn(n); cinn(w);
    for(i = 1; i <= n; i++){
        cinn(t); cinn(value[i]); cinn(need[i]);
        c[i] = t - 1;
    }
    for(i = 1; i <= n; i++){ if(c[i]){ for(j = w; j >= 0; j--){
                if(j - need[i] >= 0) dp[j] = max(dp[j], dp[j-need[i]] + value[i]);
                else break;
            }
        }
        else{
            for(j = 0; j <= w; j++){ if(j - need[i] >= 0) dp[j] = max(dp[j], dp[j-need[i]] + value[i]);
            }
        }
    }

    //cout << dp[n-1][w] << endl;
    printf("%dn", dp[w]);
    return 0;
}

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

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx