样例都过不了 , 求助
  • 板块P1776 宝物筛选
  • 楼主M_Jun
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/7/22 15:51
  • 上次更新2024/7/22 16:06:07
查看原帖
样例都过不了 , 求助
1098953
M_Jun楼主2024/7/22 15:51

样例都过不了 , 求 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;
}

2024/7/22 15:51
加载中...