求助,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];
}