讨论详情 - Tom老师的信奥小站

C++
比较学习背包问题和贪心问题
mrhowe SU @ 2024-3-16 16:24:10

暴力枚举-递归实现暴力枚举优化-带备忘递归

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int v[6]={0,10,3,4,5,4},p[6]={0,24,2,9,10,9};
int c=13;
int P[10][10];

int bl(int h ,int i ,int c1){
	if(c1<0) return -9999999;
	if(i<=0) return 0;
	if(P[i][c1]!=0){
		return P[i][c1];
	}
	int p1 = bl(h,i-1,c1-v[i])+p[i];
	int p2 = bl(h,i-1,c1);
	P[i][c1]=max(p1,p2);
	return P[i][c1];
}

int main(){
	cout<<bl(1,5,c);
	return 0;
}

动态规划解法

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
int n,p[N],v[N],c,P[N][N],rec[N][N];
int main(){
	cin>>n>>c;
	for(int i=1;i<=n;i++)cin>>p[i]>>v[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=c;j++){
			if(v[i]<=j && P[i-1][j-v[i]]+p[i]>P[i-1][j]){
				P[i][j]=P[i-1][j-v[i]]+p[i];
				rec[i][j]=1;
			}else {
				P[i][j]=P[i-1][j];
				rec[i][j]=0;
			}
		}
	}
	cout<<"最优解："<<P[n][c]<<endl;
	int k = c;
	for(int i=n;i>=1;i--){
		if(rec[i][k]==1){
			cout<<"选择商品："<<i<<endl;
			k = k-v[i];
		}else{
			cout<<"不选择商品："<<i<<endl;
		}
	}
	return 0;
}

贪心问题

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
int n,p[N],v[N],c;
double xjb[N];

int main(){
	cin>>n>>c;
	for(int i=1;i<=n;i++){
		cin>>p[i]>>v[i];
		xjb[i]=p[i]*1.0/v[i];
	}
	for(int i=1;i<=n-1;i++){
		int flag =0;
		for(int j=1;j<=n-i;j++){
			if(xjb[j]<xjb[j+1]){
				swap(xjb[j],xjb[j+1]);
				swap(p[j],p[j+1]);
				swap(v[j],v[j+1]);
				flag = 1;
			}
		}
		if(flag==0){
			break;
		}
	}
	int i=1,ans=0;
	while(c>0&&i<=n){
		if(v[i]<=c){
			ans=ans+p[i];
			c=c-v[i];
		}else{
			ans=ans+p[i]*c/v[i];
			c=0;
		}
		i++;
	}
	cout<<ans;
	return 0;
}

对比

xinao011 LV 8 @ 2024-3-17 20:29:49

#include<bits/stdc++.h>//头文件
using namespace std;//命名空间
const int N = 1e3+10;//数组大小
int v[N],p[N];//价格和体积
int n,c;//物品数量和袋子体积
int P[N][N];//"备忘录"
int bl(int h ,int i ,int c1){//暴力递归
	if(c1<0) return -9999999;//判断袋子是否满了
	if(i<=0) return 0;//判断所有物品是否全部取完
	if(P[i][c1]!=0){//判断是否已算出结果
		return P[i][c1];//用结果返回
	}
	int p1 = bl(h,i-1,c1-v[i])+p[i];//取这个物品
	int p2 = bl(h,i-1,c1);//不取这个物品
	P[i][c1]=max(p1,p2);//取更大的值并记录
	return P[i][c1];//向上返回一层
}
int main(){//主函数
	cin>>n>>c;//输入物品数量和袋子体积
	for(int i-1;i<=n;i++)cin>>v[i]>>p[i];//输入每个物品的体积和价值
	cout<<bl(1,n,c);//数出结果
	return 0;//结束程序
}