头像

坚持就是胜利_1


访客:2075

在线 



```#include [HTML_REMOVED]
using namespace std;

const int N = 110;
int n, m;
int v[N], w[N];
int f[N][N];
int h[N], e[N], ne[N], idx;
bool st[N];

void add(int a, int b){
ne[idx] = h[a]; e[idx] = b; h[a] = idx++;;
}

void dfs(int root){
for(int i, i2 = h[root]; i2 != -1; i2 = ne[i2]){///son traversal
i = e[i2]; ///注意这个e[i2]才是真正的点
if(!st[i]) dfs(i), st[i] = true;
///fenzu bag
for(int j = m; j >= 0; j–){///j values, 注意这里是j >= 0, 和v[root]没有关系
for(int k = 0; k <= j; k++){///k values’ from son
f[root][j] = max(f[root][j], f[i][k] + f[root][j-k]);
}
}
}

///下面是依赖的处理,必须买,买不起就算是0
for(int j = m; j >= v[root]; j--)  f[root][j] = f[root][j-v[root]] + w[root];
for(int j = 0; j < v[root]; j++)   f[root][j] = 0;

}

int main(){
cin>>n>>m;
int p, root;

idx = 0;    memset(h, -1, sizeof h);
for(int i = 1; i <= n; i++){
    scanf("%d%d%d", &v[i], &w[i], &p);
    if(p == -1){
        root = i;
    }else{
        add(p, i);
    }
}

memset(st, false, sizeof st);

dfs(root);

cout<<f[root][m]<<endl;

return 0;

}
```



活动打卡代码 AcWing 532. 货币系统

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110, M = 25250;
int a[N];
int f[M];
int n;

int main(){
    int T;  cin>>T;
    while(T--){
        memset(f, 0, sizeof f); f[0] = 1;
        cin>>n;
        for(int i = 0; i < n; i++){
            cin>>a[i];
        }
        sort(a, a + n);

        int v;
        int maxVal = a[n-1];
        int res = 0;
        for(int i = 0; i < n; i++){
            v = a[i];
            if(f[v] == 0)   res++;
            for(int j = v; j <= maxVal; j++){//完全包
                f[j] = max(f[j], f[j-v]);
            }
        }
        cout<<res<<endl;
    }

    return 0;
}



活动打卡代码 AcWing 7. 混合背包问题

/*
我们从dp的基本原来可知,背包的三种的类型 01, 完全,以及多重背包 dp数组的含义都是一样的
只是他们的状态转移方程不同,所以说我们根据物品,直接选择他们对应的状态转移方程就可以了
不对,考虑到时间效率问题,多次背包选择二进制优化即可
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010;
int f[N];
int n, m;

int main(){
    cin>>n>>m;
    int v, w, s;
    for(int i = 0; i < n; i++){
        cin>>v>>w>>s;
        if(s == 0){ ///wan quan bag
            for(int j = v; j <= m; j++){
                f[j] = max(f[j], f[j-v]+w);
            }
        }else{
            if(s == -1) s = 1;
            for(int k = 1; k <= s; k = k * 2){
                for(int j = m; j >= k * v; j--){    //0-1bag
                    f[j] = max(f[j], f[j-k*v]+k*w);
                }
                s -= k;
            }
            if(s){
                for(int j = m; j >= s * v; j--){    //0-1bag
                    f[j] = max(f[j], f[j-s*v]+s*w);
                }
            }
        }
    }

    cout<<f[m]<<endl;
    return 0;
}



活动打卡代码 AcWing 1021. 货币系统

/*
f[i][j] = fi-1][j] + f[i-1][j-v] + ...
-->f[i][j] = f[i-1][j] + f[i][j-v]
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

const int M = 3030;
LL f[M];
int n, m;

int main(){
    cin>>n>>m;

    f[0] = 1;
    int v;
    for(int i = 0; i < n; i++){
        cin>>v;
        for(int j = v; j <= m; j++){
            f[j] += f[j-v];
        }
    }

    cout<<f[m]<<endl;

    return 0;
}


活动打卡代码 AcWing 426. 开心的金明

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

const int N = 30300;
int f[N];

int main(){
    int n, m;
    cin>>n>>m;
    int v, p;
    for(int i = 0; i < m; i++){
        cin>>v>>p;
        p = p * v;
        for(int j = n; j >= v; j--){
            f[j] = max(f[j], f[j-v]+p);
        }
    }

    cout<<f[n]<<endl;
    return 0;
}



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

typedef pair<int, int> PII;

const int N = 32010, M = 65;
int f[N];
PII master[M];
vector<PII> servant[M];
int n, m;

int main(){
    cin>>n>>m;
    int v, p, q, w;
    for(int i = 1; i <= m; i++){
        cin>>v>>p>>q;
        p = p * v;  //提前进行预处理
        if(q == 0){
            master[i] = {v, p};
        }else{
            servant[q].push_back({v, p});
        }
    }

    for(int i = 1; i <= m; i++){///master, master = 0也不会影响
        for(int j = n; j >= master[i].first; j--){
            //v = master[i].first, w = master[i].second;
            //f[j] = max(f[j], f[j-v] + w);       ///不买和买一个主件
            for(int k = 0; k < 1 << servant[i].size(); k++){///下面是对买主件和附件的遍历
                v = master[i].first, w = master[i].second;  ///主件放上去
                for(int k2 = 0; k2 < servant[i].size(); k2++){///附件选与不选直接使用二进制
                    if((k >> k2) & 1)   v += servant[i][k2].first, w += servant[i][k2].second;
                }
                if(j >= v)  f[j] = max(f[j], f[j-v] + w);
            }

        }
    }

    cout<<f[n]<<endl;

    return 0;
}


活动打卡代码 AcWing 1013. 机器分配

/*
这个分组背包问题条件有些隐含的,
f[i][j]:j台机器,分配给前i个公司,所能够获得的最大盈利
f[i][j] = f[i-1][j-0]+, f[i-1][j-1]+,...
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int q[N][N], f[N][N];

int n, m;

int main(){
    cin>>n>>m;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin>>q[i][j];
        }    
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            f[i][j] = f[i-1][j];
            for(int k = 1; k <= j; k++){
                if(f[i][j] < f[i-1][j-k]+q[i][k]){
                    f[i][j] = f[i-1][j-k]+q[i][k];
                }
            }
        }
    }
    cout<<f[n][m]<<endl;

    int j = m;
    vector<int> path;
    for(int i = n; i; i--){
        for(int k = 0; k <= j; k++){
            if(f[i][j] == f[i-1][j-k]+q[i][k]){
                path.push_back(k);  j -= k; break;
            }
        }       
    }
    reverse(path.begin(), path.end());

    for(int i = 0; i < path.size(); i++)    cout<<i+1<<" "<<path[i]<<endl;

    return 0;
}




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

const int N = 1010;
int f[N][N];
int g[N][N];
int w[N], v[N];
int n, m;
/*
g[i][j]表示的是 f[i][j]是从哪里来的;
但是后往前不可,我们需要变形,一下,“前往后”,实际上也就是变一下顺序
*/
int main(){
    cin>>n>>m;
    for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);

    for(int i = n; i; i--){///为了字典序才这样的
        for(int j = 0; j <= m; j++){
            g[i][j] = 0;
            f[i][j] = f[i+1][j];            ///不选
            if(j >= v[i] && f[i][j] <= f[i+1][j-v[i]]+w[i]){///选, 能选就选,才会最小
                g[i][j] = 1;
                f[i][j] = f[i+1][j-v[i]] + w[i];
            }
        }
    }
    /*
    int j = m;
    for(int i = 1; i <= n; i++){
        if(g[i][j]){
            cout<<i<<" ";
            j -= v[i];
        }else{
            ;
        }
    }
    */
    ///也可以不使用g[i][j];

    int j = m;
    for(int i = 1; i <= n; i++){
        if(j-v[i] >= 0 && f[i][j] == f[i+1][j-v[i]]+w[i]){///注意这个判别条件
            cout<<i<<" ";
            j -= v[i];
        }else{
            ;
        }
    }

    cout<<endl;
    return 0;
}


活动打卡代码 AcWing 1019. 庆功会

/
多重背包,三种方法
O(NMS):ok
O(NMlog(S))–>01bag
O(NM)
/

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

const int N = 550, M = 6050;
int n, m;
int f[M];

int main(){
    cin>>n>>m;
    int v, w, s;
    for(int i = 0; i < n; i++){
        scanf("%d%d%d", &v, &w, &s);
        for(int j = m; j >= v; j--){
            for(int k = 0; k <= s && k * v <= j; k++){
                f[j] = max(f[j], f[j-k*v]+k*w);
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}



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

const int N = 1010, M = 110;
int n, m1, m2;
int f[M][M];
/*
f[i][j][k]:前i个物品, <= j, <= k的时候,最大的价值
*/
int main(){
    cin>>n>>m1>>m2;
    int v1, v2, w;
    for(int i = 0; i < n; i++){
        cin>>v1>>v2>>w;
        for(int j = m1; j >= v1; j--){
            for(int k = m2; k >= v2; k--){
                f[j][k] = max(f[j][k], f[j-v1][k-v2]+w);
            }
        }
    }

    cout<<f[m1][m2]<<endl;
    return 0;
}