能帮我看看多重背包(二进制优化)哪里写错了吗?
  • 板块学术版
  • 楼主joe_zxq
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/1/9 20:15
  • 上次更新2024/1/9 20:19:16
查看原帖
能帮我看看多重背包(二进制优化)哪里写错了吗?
623577
joe_zxq楼主2024/1/9 20:15

能帮我看看多重背包(二进制优化)哪里写错了吗?一直 TLE\texttt{TLE}

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

#define ll long long

ll c, n, wi, vi, si, dp[114514];
vector<ll> w, v;

int main() {
    
    clock_t start = clock();
    
    w.push_back(0);
    v.push_back(0);
    cin >> c >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> si >> wi >> vi;
		ll t = 1; 
		while (t <= si) {
		    w.push_back(t * wi);
		    v.push_back(t * vi);
		    si -= t;
		    t *= 2;
		}
		for (ll j = 0; j < si; j++) {
		    w.push_back(wi);
		    v.push_back(vi);
		}
    }

    for (ll i = 1; i < (ll)w.size(); i++) {
        for (ll j = c; j >= w[i]; j--) {
        	dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    cout << dp[c];
    
    return 0;
}
2024/1/9 20:15
加载中...