求助大佬，30分，分组背包。祝帮忙的大佬都能AK自己梦想的比赛

P1064 [NOIP2006 提高组] 金明的预算方案

retamian @ 2023-09-02 20:15:57

原题链接：P1064 [NOIP2006 提高组] 金明的预算方案

感谢帮忙debug的大佬，代码30分，前三点AC，后面WA，分组背包

#include <iostream>
using namespace std;
const long long N = 100, M = 3.2e4 + 10;
long long v[N][5], w[N][5];//只选主件、选主件+附件1、选主件+附件2、选主件+附件1+附件2、不选五种情况花费money和可取得的价值
long long dp[M];
long long cnt;
int main() {
    long long money, n;
    cin >> money >> n;
    for (long long i = 1; i <= n; i++) {//分组的处理
        long long m, pi, zhu;
        cin >> m >> pi >> zhu;
        if (zhu == 0) {
            v[++cnt][0] = m;
            w[cnt][0] = m * pi;
        } else {
            if (v[zhu][1] == 0) {
                v[zhu][1] = m + v[zhu][0];
                w[zhu][1] = m * pi + w[zhu][0];
            } else {
                v[zhu][2] = m + v[zhu][0];
                w[zhu][2] = m * pi + w[zhu][0];
                v[zhu][3] = m + v[zhu][1];
                w[zhu][3] = m * pi + w[zhu][1];
            }

        }
    }

    for (long long i = 1; i <= cnt; i++) {
        for (long long k = money; k >= 1; k--) {
            for (long long j = 0; j <= 4; j++) {
                if (v[i][j] <= k)
                    dp[k] = max(dp[k], dp[k - v[i][j]] + w[i][j]);
            }
        }
    }

    cout << dp[money];
    return 0;
}

参考数据 #4

样例输入

4500 12
100 3 0
400 5 0
300 5 0
1400 2 0
500 2 0
800 2 4
1400 5 4
300 5 0
1400 3 8
500 2 0
1800 4 0
440 5 10

样例输出

16700

该程序输出

16100

by bzzltl @ 2023-09-03 20:42:36

@retamian 你进行分组的时候，zhu和cnt弄混了

#include <iostream>
using namespace std;
const long long N = 100, M = 3.2e4 + 10;
long long v[N][5], w[N][5];//只选主件、选主件+附件1、选主件+附件2、选主件+附件1+附件2、不选五种情况花费money和可取得的价值
long long dp[M];
long long cnt;
long long belong[N];
int main() {
    long long money, n;
    cin >> money >> n;
    for (long long i = 1; i <= n; i++) {//分组的处理
        long long m, pi, zhu;
        cin >> m >> pi >> zhu;
        if (zhu == 0) {
            v[++cnt][0] = m;
            w[cnt][0] = m * pi;
            belong[i]=cnt;
        } else {
            zhu=belong[zhu];
            if (v[zhu][1] == 0) {
                v[zhu][1] = m + v[zhu][0];
                w[zhu][1] = m * pi + w[zhu][0];
            } else {
                v[zhu][2] = m + v[zhu][0];
                w[zhu][2] = m * pi + w[zhu][0];
                v[zhu][3] = m + v[zhu][1];
                w[zhu][3] = m * pi + w[zhu][1];
            }

        }
    }

    for (long long i = 1; i <= cnt; i++) {
        for (long long k = money; k >= 1; k--) {
            for (long long j = 0; j <= 4; j++) {
                if (v[i][j] <= k)
                    dp[k] = max(dp[k], dp[k - v[i][j]] + w[i][j]);
            }
        }
    }

    cout << dp[money];
    return 0;
}

by retamian @ 2023-09-03 21:07:56

@bzzltl 感谢大佬，debug2天都没看出问题，祝大佬rp++，关注了

献上膜拜：%%%

|