背包问题求助
  • 板块学术版
  • 楼主LookatSea
  • 当前回复12
  • 已保存回复12
  • 发布时间2023/10/7 17:47
  • 上次更新2023/11/2 15:02:37
查看原帖
背包问题求助
943493
LookatSea楼主2023/10/7 17:47

题意:有多组用例,每个用例包含5个整数,分别是背包的容量,第一个物品的大小和价值,第二个物品的大小和价值(只有两个物品,数量无限),问装的物品最大的价值是几?

代码:

#include<bits/stdc++.h>
using namespace std;
int s[100010] ,v[100010],k[100010];
int fun(int n,int m){
	s[100010]=v[100010]=k[100010]={0}; 
	for(int i=1;i<=n;i++){
		cin>>v[i]>>k[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=v[i];j<=m;j++){
			s[j]=max(s[j],s[j-v[i]]+k[i]);
		}
	}
	return s[m];
}
signed main(){
	int n=2,m;
	int ioioio;
	cin>>ioioio;
	for(int i=1;i<=ioioio;i++){
		cin>>m;
		int oioioi=fun(n,m);
		printf("Case #%d: %d\n",i,oioioi);
	}
	
	return 0;
}

2023/10/7 17:47
加载中...