android开发实战 Zookeeper使用 HashMap extjs6.5 Java包装类 金融信贷 silverlight request textview swagger jquery绑定事件的方法 删除数组第一个元素 oracle限制查询条数 拼接json字符串 maven配置eclipse svn更新本地代码 mysql建表 python写脚本 java包 java获取现在时间 java泛型的使用 java获取 linux基础教程 sql实例 java游戏制作 局域网助手 音频频谱分析软件 EasyCHM 神龙激活 快点蛆虫成就单刷 疯狂java讲义 用流量打电话的软件 js关闭当前页面 视频解析软件 dxsetup tomcat修改端口 dnf瞎子传说套选择 php正则匹配 jq改变css样式 游戏linux正则表达式
当前位置: 首页 > 学习教程  > 编程语言

2020 8.3 暑期 背包专题

2020/8/11 20:55:23 文章标签:

01 背包从前i个物品中选择总重量小于W 的总价值最大

//二维的写法
int dp[N][M];
for(int i=1;i<=n;i++)
for(int j=0;j<=W;j++)
if(j<w[i]) dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
cout<<dp[n][W];

 

 

//一维的写法
int dp[M];
for(int i=1;i<=n;i++)
for(int j=W;j>=w[i];j--)// 注 意 内 层 循 环 的 方 向
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
cout<<dp[W];

 

 完全背包

在 01 背包的基础上任何物品可以取无数次

//二维写法
int dp[N][M];
for(int i=1;i<=n;i++)
for(int j=0;j<=W;j++)
if(j<w[i]) dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
cout<<dp[n][W];

 

//一维写法
int dp[M];
for(int i=1;i<=n;i++)
for(int j=w[i];j<=W;j++)// 注 意 内 层 循 环 的 方 向
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
cout<<dp[W];

 

 

题目连接:

https://vjudge.net/contest/388683#overview

 

 

A - Bone Collector

 

 

模板

#include<iostream>
#include<cstring>

using namespace std;

const int N=1100;
int f[N];
int v[N],w[N];//价值和重量 
int t;
int n,W; 

int main()
{
	cin>>t;
	while(t--){
		memset(f,0,sizeof f);
		cin>>n>>W;
		for(int i=1;i<=n;i++) cin>>v[i];
		for(int i=1;i<=n;i++) cin>>w[i];
		for(int i=1;i<=n;i++){
	 		for(int j=W;j>=w[i];j--)
				f[j]=max(f[j],f[j-w[i]]+v[i]); 
		}
		cout<<f[W]<<endl;
	}
	
	return 0;
 } 

 

 

B - Robberies

 

转化为安全系数,01背包是使价值最大(所选重量不超过j),而这个是抢的钱最多而且还要使安全系数最大

 

 

code:

#include<iostream>
#include<cstdio>

using namespace std;
const int N =1e4+10;
double f[N];//表示钱为i时的安全性 
int n ,sum;
double P;
struct node{
	int m;
	double p;
}num[N]; 

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0); 
	int t;
	cin>>t;
	while(t--){
		cin>>P>>n;
		P=1-P; 
		for(int i=0;i<N;i++) f[i] =0;
		f[0]=1; 
		sum=0;
		for(int i=1;i<=n;i++){
			cin>>num[i].m>>num[i].p;	
			sum+=num[i].m;
		} 
		for(int i=1;i<= n;i++)
			for(int j=sum;j>=num[i].m;j--){
				f[j]=max(f[j],f[j-num[i].m]*(1-num[i].p));
			} 
		for(int i=sum;i>=0;i--)
		{
			if(f[i]>P){
				cout<<i<<"\n";
				break;
			}
		}
	}
	
	
	return 0;
 } 

 

C - 饭卡

 

除去一个最大值,剩下的n-1个选择总量不超过m-5的最大价值不就是01 背包吗

code:

#include<iostream>
#include<cstdio>

using namespace std ;

const int N=1100;

int w[N];
int n,m;
int f[N];
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	while(cin>>n&&n){
		for(int i=1;i<=n;i++) cin>>w[i];
		cin>>m;
		if(m<5){
			cout<<m<<"\n"; 
			continue;
		}
	 	int k,maxx=0;
		for(int i=1;i<=n;i++){
			if(w[i]>maxx){
				maxx=max(maxx,w[i]);//找到最大值 
				k=i;
			}
		}
		for(int i=0;i<N;i++) f[i] =0;
		for(int i=1;i<=n;i++){
			if(k==i) continue;
			for(int j=m-5;j>=w[i];j--){
				f[j]=max(f[j],f[j-w[i]]+w[i]);
			}
		}
		cout<<m-f[m-5]-maxx<<"\n"; 
	}
	
	
	return 0;
}

 

 

 

D - Piggy-Bank

 

 

#include<iostream>
#include<cstdio>
#define INF 0x3f3f3f3f

using namespace std;

const int N=1e4+10;
int n;
int E,F; 
int W;
int t;
int f[N];
int v[550],w[550];
int main()
{
	scanf("%d",&t);
	while(t--){ 
		scanf("%d%d",&E,&F);
		W=F-E; 
		scanf("%d",&n);
		for(int i=1;i<=n;i++) {
			scanf("%d%d",&v[i],&w[i]);
		}
		for(int i=1;i<N;i++){
			f[i]=INF;
		}
		f[0]=0;
		for(int i=1;i<= n;i++)
			for(int j =w[i];j<=W;j++){
				f[j]=min(f[j],f[j-w[i]]+v[i]);
			}
		if(f[W]==INF) printf("This is impossible.\n");
		else printf("The minimum amount of money in the piggy-bank is %d.\n",f[W]);
	}
	
	return 0;
}

 

 

E - 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活

多重背包模板

 

 

#include<iostream>
#include<cstdio>

using namespace std;

const int N =200;

int f[N];
int n,m; 
int v[N],w[N],s[N];
int main()
{
	int t;
	scanf("%d",& t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++) scanf("%d%d%d",&w[i],&v[i],&s[i]);
		for(int i=0;i<N;i++) f[i]=0;
		for(int i=1;i<=m;i++){
			for(int k=1;s[i]>0;k<<=1){
				int mul =min(s[i],k);
				for(int j=n;j>=mul*w[i];j--){
					f[j]=max(f[j],f[j-mul*w[i]]+mul*v[i]); 
				}
				s[i]-=mul;
			}
		}
		printf("%d\n",f[n]);
	}
	
	return 0;
}

 

 

F - 钱币兑换问题

 

方案数是相加

code:

#include<iostream>
#include<cstdio>

using namespace std;

const int N=4e4+10;

int f[N];
int n;
int main()
{
	
	while(~scanf("%d",&n)){
		for(int i=1;i<N;i++) f[i]=0;
		f[0]=1;
		for(int i=1;i<=3;i++){
			for(int j=i;j<=n;j++){
				 f[j]=f[j]+f[j-i];
			}
		}
		printf("%d\n",f[n]);		
	}

	return 0;
}

 


本文链接: http://www.dtmao.cc/news_show_100438.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?