问:
完全背包(本题)优化成一维dp数组后为什么不像01背包(P1048采药)那样反向枚举?
本题:{
int main(){
int T,M;
int f[10000010];
int a[10100];
int b[10010];
cin>>T>>M;
for(int i=1;i<=M;i++)
cin>>a[i]>>b[i];
for(int i=1;i<=M;i++){
for(int j=a[i];j<=T;j++){
f[j]=max(f[j],f[j-a[i]]+b[i]);
}
}
cout<<f[T];
return 0;
}
}
01(P1048采药){
#include<bits/stdc++.h>
using namespace std;
int f[1010];
int main(){
int T,M,t1,m1;
cin>>T>>M;
for(int i=1;i<=M;i++){
cin>>t1>>m1;
for(int j=T;j>=t1;j--){
f[j]=max(f[j-t1]+m1,f[j]);
}
}
cout<<f[T];
return 0;
}
}
Why?
Whyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy?