多重背包
  • 板块题目总版
  • 楼主Carrot_Rui
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/4/2 16:59
  • 上次更新2023/11/5 01:09:58
查看原帖
多重背包
376481
Carrot_Rui楼主2021/4/2 16:59

大佬你帮帮我这个简单题(我不会)

原题

#include <iostream>

using namespace std;

const int N = 26002;
//最大是2000 * log1000

int f[N], w[N], v[N], m , n, n1;

int main(){
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        int x,y,s, t = 1;
        cin>>x>>y>>s;
        while(s >= t){
            v[++n1] = x * t;
            w[n1] = y * t;
            s -= t;
            t *= 2;
        }
        if(s > 0) v[++n1] = x * s, w[n1] = y * s;
    }
    
    for(int i = 1; i <= n1; i ++ )
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j],f[j-v[i]] + w[i]);
            
    cout<<f[m]<<endl;
    return 0;
}
2021/4/2 16:59
加载中...