背包遍历顺序求助
查看原帖
背包遍历顺序求助
504142
micmic楼主2022/3/29 16:08

求助,j的到底是从后往前还是从前往后遍历哇,想不明白

#include<iostream>
#include<string>
using namespace std;
//背包有21格 
int m;	//一开始背包里的东西
int n;	//卖n种物品
int a[105];	//每个物品的数量
int b[105];	//每个物品的价值
int c[105];	//1格可以放多少个
string st[105];	//名字 

//也就是现在背包还剩21-m格,要在这个基础上把最大价值的物品组合放进背包 

int dp[105][25]; //dp[i][j]代表把前i种物品放入容量为j个格子的背包能获得的最大价值
//格数问题在这解决!! 
//有a个,每格最多放x个,返回值是它占多少格儿 
int upint(int a,int x){
	int r=x;
	while(1){
		//能放下a个时,返回r/x 
		if(r>=a) return r/x;
		//还放不下,就扩大一倍 
		r+=x;
	} 
}

int main(){
	cin>>m>>n;
	int cnt=0;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i]>>c[i]>>st[i];
		int flag=0;
		for(int j=1;j<=i-1;j++)
			if(st[j]==st[i]){
				a[j]+=a[i];
				flag=1;
				break;
			}
		
		if(flag==0)cnt++;
	}
			
	m=21-m; //当前背包所剩格子数 

	
	//每 种 物品 
	for(int i=1;i<=cnt;i++){
		//背包格子数 
		for(int j=m;j>=0;j--){
			//这种物品的件数 
			for(int k=0;k<=a[i];k++){
					int w=upint(k,c[i]);
					if(j>=w)
						dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+k*b[i]);
				
			}
		} 
	}	
	
	cout<<dp[n][m];
	
}
2022/3/29 16:08
加载中...