Submission #1106332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106332		GuessWhoHas2Cats	Knapsack (NOI18_knapsack)	C++14	73 / 100	192 ms	262144 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int W, n; 
    cin >> W >>  n;
    vi vals(n), wes(n), copies(n);
    for(int i = 0; i < n ; i ++)
    {
        cin >> vals[i] >> wes[i] >> copies[i];
    }
    // vvi dp(n + 1, vi(W + 1, 0));
    vvi dp(n + 1, vi(W + 1, 0));
    for(int i = 1; i <= n; i ++)
    {
        int &val = vals[i - 1], &we = wes[i - 1], &cop = copies[i - 1];
        for(int j = 0; j <= W; j ++)
        {
            for(int k = 0; (k <= cop) && (k * we <= j); k ++)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * we] + k * val);
        }
    }
    // for(int j = 0; j < W + 1; j ++)
    // {
    //     for(int i = 1; i <= n; i ++)
    //     {
    //         int &val = vals[i - 1], &we = wes[i - 1], &cop = copies[i - 1];
    //         for(int k = 0; (k < cop) && (k * we <= j); k ++)
    //             dp[i][j] = max(dp[i][j], dp[i - 1][j - k * we] + k * val);
    //     }
    // }
    cout << dp[n][W];
}
// 第一次错误原因： 对于 k 的遍历 k <= cop
// 上面已经很完整了，对比KSol.cpp, KSol.cpp有些逻辑冗余了。

// 要优化这段多重背包问题的代码，可以使用一些经典的优化技巧来减少时间复杂度，尤其是避免在内部循环中使用重复计算。下面是一些可以应用的优化方法：

// 优化思路
// 二进制拆分法：利用二进制拆分来减少物品数量的计算。这种方法将一个物品的多个副本转化为若干个较小数量的副本，从而减少内层循环的迭代次数。

// 滚动数组：由于只需要上一行的 dp 状态，可以使用滚动数组来减少空间复杂度。

// -》 Optimize_knapsack.cpp -> 过不了，只能过17/100个样例，删了

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27