样例都过不了 , 求 DALAO 帮忙调试
小破源码 :
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#define INF 0x7fffffff
#define int long long
#define re register
#define in inline
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std ;
int W , n ;
int v[105] , w[105] , m[105] ;
int dp[40005] ;
void Complete_Pack(int w , int v) {// 完全背包
for(re int i = 1 ; i <= w ; i ++) {
dp[i] = max(dp[i] , dp[i - w] + v) ;
}
}
void Zero_one_Pack(int w , int v) {// 01背包
for(re int i = w ; i >= 1 ; i --) {
dp[i] = max(dp[i] , dp[i - w] + v) ;
}
}
void Multiple_Pack(int w , int v , int num) { // 多重背包
if(w * num >= v) {
Complete_Pack(w * num , v) ;
// cout << "1\n";
} else {
re int cnt = 1 ;
while(cnt < num) {
Zero_one_Pack(cnt * w , cnt * v) ;
num -= cnt ;
cnt *= 2 ;
}
// cout << "2\n";
Zero_one_Pack(cnt * w , cnt * v) ;
}
}
signed main ( ) {
ios ;
cin >> n >> W ;
for(re int i = 1 ; i <= n ; i ++) {
cin >> v[i] >> w[i] >> m[i] ;
}
for(re int i = 1 ; i <= n ; i ++) {
// cout << "3\n";
Multiple_Pack(w[i] , v[i] , m[i]) ;
}
cout << dp[n] << '\n' ;
return 0;
}