宝物筛选 题解

多重背包的模版题，详细在关于多重背包问题(入门) 笔记

#include<bits/stdc++.h>
using namespace std;
int n,W;//n个种数,W载重 
struct Node{int v,w,m;}a[500005];//v价值w重量m可买数量,注意数据范围
int DP[600005];//当载重为j下所能获得的最大价值 
int main(){
	cin>>n>>W;
	int pos=0;//转化后的长度 
	for(int i=1;i<=n;i++){
		int v1,w1,m1,k=1;//k代表2的幂,即一次拆分出的量 
		cin>>v1>>w1>>m1;
		while(k<=m1){
			pos++;
			a[pos].v=v1*k;
			a[pos].w=w1*k;
			m1-=k;
			k*=2;
		} 
		if(m1){//如果m1中还有没拆分的，剩下的直接为一组 
			pos++;
			a[pos].v=v1*m1;
			a[pos].w=w1*m1; 
		}
	}
	for(int i=1;i<=pos;i++){//01背包
		for(int j=W;j>=a[i].w;j--){
			DP[j]=max(DP[j],DP[j-a[i].w]+a[i].v);
		} 
	}
	cout<<DP[W];
	return 0;
}