求问:完全背包和01背包区别
查看原帖
求问:完全背包和01背包区别
946209
Xumingjun0405楼主2025/1/20 10:02

问: 完全背包(本题)优化成一维dp数组后为什么不像01背包(P1048采药)那样反向枚举?

本题:{

int main(){

	int T,M;
  int f[10000010];//dp
  
  int a[10100];//time
 
  int b[10010];//value

	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++){//正向枚举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--){//反向枚举j
			f[j]=max(f[j-t1]+m1,f[j]);
		}
	}
	cout<<f[T];
	return 0;
}

}

Why?

Whyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy?

2025/1/20 10:02
加载中...