[编程题]今天要吃点好的！
- 热度指数：1747 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
加班了一个通宵的度度熊，神经有点恍惚，想到依然未能解决的Bug，眼泪禁不住霹雳哗啦往下掉……他抬头看了看帝都灰蒙蒙的天空，一咬牙，一跺脚，大叫一声——劳资今天要吃点好的！ 已知本厂有n个食堂，第i（i属于[1,n])个食堂有m[i]种食物，每种食物有一个价钱c，享受度v，度度熊希望去一个食堂就餐，花费[bot,top]范围内的钱数（也可以拍桌子走人，哪里都不吃了），选择若干种食物，使得自己所能获得的享受度最大。（注意，度度熊还有一个挑食的特点，同一种食物他最多只会点一份。） 现在告诉你所有食堂食物的信息，希望你进行选择搭配，使得度度熊可以得到最大的享受度，并输出这个享受度的值。
输入描述:
第一行是一个正整数T（1<=T<=20),表示有T组测试数据。
对于每组数据——
第一行是三个数n，bot，top，n代表食堂数1<=n<=10），bot是这次吃饭的最低消费，top是这次吃饭的最高消费（0<=bot，top<=10000）
接下来依次是n个食堂的信息，对于第i个食堂
第一行是一个数m[i]（o<=m[i]<=100)，代表第i个食堂的食物数
第二行有2*m[i]个数，分别是c[i][1]，v[i][1]，c[i][2]，v[i][2]，……c[i][m[i]]，v[i][m[i]]
c[i][j]表示第i个餐厅第j种食物的价钱，v[i][j]代表第i个餐厅第j种食物给度度熊带来的享受度。
输出描述:
对于每组数据，请输出一行，每行一个正整数。表示度度熊所能获得的最大享受度。
数据结果保证不会超过2^31-1.
示例1
输入
2<br/>2 10 20<br/>5 1 1 2 1 5 1 10 1 20 1<br/>5 1 2 2 2 5 2 10 2 20 2<br/>2 10 10<br/>1 5 1<br/>1 5 1
输出
8<br/>0
#include <cstdlib>
#include <iostream>
#define M 105
#define V 10005
#define INF 0x3f3f3f3f
using namespace std;
int main()
{
int T;
cin >>T;
while(T--){
int n, bot, top, ans=0;
cin >>n >>bot >>top;
while(n--){
int m, c, v, dp[V]={0};
for(int j=0; j<=top; j++)
dp[j] = -INF;
dp[0] = 0; //装满背包
cin >>m;
for(int i=0; i<m; i++){
cin >>c >>v;
for(int j=top; j>=c; j--)
dp[j] = max(dp[j], dp[j-c]+v);
}
for(int j=bot; j<=top; j++)
ans = max(ans, dp[j]);
}
cout <<ans <<endl;
}
//system("PAUSE");
return 0;
}
发表于 2015-09-09 12:08:44
回复(8)
import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub /* * 百度笔试，度度熊吃饭 */ int testDataCount=0,diningHallCount=0; Scanner scan=new Scanner(System.in); testDataCount=scan.nextInt(); int mostEnjoy[]=new int[testDataCount]; for(int i=0;i<testDataCount;i++){ int bot=0,top=0; diningHallCount=scan.nextInt(); int diningEnjoy[]=new int[diningHallCount]; bot=scan.nextInt(); top=scan.nextInt(); for(int j=0;j<diningHallCount;j++){ int foodCount=scan.nextInt(); int AllFood[][]=new int [foodCount+1][top+1]; int []foodCast=new int[foodCount+1]; int []foodEnjoy=new int[foodCount+1]; for(int k=1;k<=foodCount;k++){ foodCast[k]=scan.nextInt(); foodEnjoy[k]=scan.nextInt(); } //System.out.println(Algotithm.baiduDuDuXiong(AllFood, foodCast, foodEnjoy, foodCount, top,bot)); diningEnjoy[j]=baiduDuDuXiong(AllFood, foodCast, foodEnjoy, foodCount, top,bot); } int mostDiningEnjoy=-1; for(int l=1;l<diningHallCount;l++){ mostDiningEnjoy=(diningEnjoy[l]>diningEnjoy[l-1])?diningEnjoy[l]:diningEnjoy[l-1]; diningEnjoy[l]=mostDiningEnjoy; //System.out.println("mostDiningE--"+mostDiningEnjoy); } mostEnjoy[i]=mostDiningEnjoy; } for(int m=0;m<testDataCount;m++){ System.out.println(mostEnjoy[m]); } } static int baiduDuDuXiong(int AllFood[][],int foodCast[],int foodEnjoy[],int foodCount,int top,int bot){ int allCost=0; for(int i=1;i<=foodCount;i++){ for(int j=1;j<=top;j++){ if(j>=foodCast[i] ){ AllFood[i][j]=AllFood[i-1][j]>(AllFood[i-1][j-foodCast[i]]+foodEnjoy[i])?AllFood[i-1][j]:(AllFood[i-1][j-foodCast[i]]+foodEnjoy[i]); }else{ AllFood[i][j]=AllFood[i-1][j]; } } } // // for(int i=0;i<=foodCount;i++){ // for(int j=0;j<=top;j++){ // System.out.print(AllFood[i][j]+" "); // } // // System.out.println(); // } return AllFood[foodCount][top]==AllFood[foodCount][bot-1]?0:AllFood[foodCount][top]; } }
编辑于 2015-09-20 17:38:46
回复(0)
是01背包问题，准确的说是“恰好装满01背包问题”，所以初始化的时候除了dp[0]=0外，其他全部初始化为负无穷（不强调恰好装满初始化为0）。这是因为消费的时候有最低消费，如果没有最低消费就是普通01背包问题。
发表于 2015-09-11 15:36:37
回复(1)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int testCount = scanner.nextInt();
for (int i = 0; i < testCount; i++) {
int messCount = scanner.nextInt();
Meal meal = new Meal(messCount, scanner.nextInt(), scanner.nextInt());
for (int j = 0; j < messCount; j++) {
int foodCount = scanner.nextInt();
Mess mess = new Mess(foodCount);
for (int t = 0; t < foodCount; t++) {
mess.allFood[t] = new Food(scanner.nextInt(), scanner.nextInt());
}
meal.messes[j] = mess;
}
System.out.println(meal.eat());
}
}
static class Meal {
Mess[] messes;
int bot;
int top;
public Meal(int count, int bot, int top) {
this.bot = bot;
this.top = top;
messes = new Mess[count];
}
public int eat() {
int enjoy = 0;
for (int i = 0; i < messes.length; i++) {
int tmp = messes[i].eat(bot, top);
if (tmp > enjoy)
enjoy = tmp;
}
return enjoy;
}
}
static class Mess {
int foodCount;
Food[] allFood;
public Mess(int count) {
this.foodCount = count;
allFood = new Food[count];
}
public int eat(int bot, int top) {
int[][] r = new int[foodCount][top + 1];
for (int i = 0; i <= top; i++) {
if (i >= allFood[0].price)
r[0][i] = allFood[0].joy;
else
r[0][i] = 0;
}
for (int i = 1; i < foodCount; i++) {
for (int j = 0; j <= top; j++) {
if (j < allFood[i].price)
r[i][j] = r[i - 1][j];
else
r[i][j] = Math.max(r[i - 1][j], r[i - 1][j - allFood[i].price]
+ allFood[i].joy);
}
}
return r[foodCount-1][bot - 1] == r[foodCount-1][top] ? 0 : r[foodCount-1][top];
}
}
static class Food {
int price;
int joy;
public Food(int price, int joy) {
this.price = price;
this.joy = joy;
}
}
}
发表于 2015-09-06 16:11:22
回复(1)
#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int counts;
int n, bot, top;
int m, c, v;
int res = 0;
while (cin >> counts) {
for (int temp = 0; temp < counts; temp++) {
cin >> n >> bot >> top;
res = 0; //清空
for (int i = 0; i < n; i++) {
cin >> m; //食堂中菜的个数
//恰好01背包问题
//初始化 dp[0] = 0, 其余初始值为INT_MIN，表示不可取
vector<int> dp(top + 1, INT_MIN);
dp[0] = 0;
for (int j = 0; j < m; j++) {
cin >> c >> v; //价格和享受度
for (int k = top; k >= c; k--) {
//价格低于c的消费情况，和该道菜无关
dp[k] = max(dp[k], v + dp[k - c]);
}
}
for (int i = bot; i <= top; i++) {
res = max(res, dp[i]);
}
}
cout << res << endl;
}
}
return 0;
}
发表于 2017-08-31 20:10:26
回复(0)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
struct food {
int c;
int v;
};
int getMaxValue(std::vector<food> foods, int bot, int top) {
int rows = foods.size();
int clos = top + 1;
std::vector<std::vector<int> > dp(rows, std::vector<int>(clos, 0));
for (int i = 1; i < rows; i++) {
for (int j = 1; j < clos; j++) {
if (j >= foods[i].c) {
dp[i][j] = std::max(dp[i - 1][j - foods[i].c] + foods[i].v, dp[i - 1][j]);
}
else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[rows - 1][top] == dp[rows - 1][bot - 1] ? 0 : dp[rows - 1][top];
}
int main() {
using namespace std;
int t;
cin >> t;
while (t--) {
int n, bot, top;
cin >> n >> bot >> top;
vector<int> m(n);
int ans = 0;
for (int i = 0; i < n; i++) {
cin >> m[i];
vector<food> foods(m[i] + 1);
for (int j = 1; j <= m[i]; j++) {
cin >> foods[j].c >> foods[j].v;
}
int temp = getMaxValue(foods, bot, top);
if (ans < temp) {
ans = temp;
}
}
cout << ans << endl;
}
return 0;
}
1维dp也是没想出来，整了个2维的。
发表于 2017-06-22 14:59:57
回复(1)
#include <iostream>
#include <stdlib.h>
#define N 10
#defile F 100
using namespace std;
int bot,top;
int n;
struct food{
int price;
int joy;
};
void sorting(struct food Food[],int size){
int i=0,j=0;
struct food Temp;
for(i=0;i<size-1;i++){
for(j=i+1;j<size;j++){
if((double)Food[i].joy/(double)Food[i].price<
(double)Food[j].joy/(double)Food[j].price){
Temp=Food[i];
Food[i]=Food[j];
Food[j]=Temp;
}
}
}
}
int getMaxJoy(struct food Food[],int size){
sorting(Food,size);
int i=0,j=0;
int maxJoy=Food[0].price;
int tmp;
for(i=0;i<size-1;i++){
if(maxJoy<bot){
maxJoy+=Food[i+1].price;
}
else if(maxJoy>top){
tmp=Food[i].price;
maxJoy=maxJoy-tmp+Food[i+1].price;
}
}
return maxJoy;
}
编辑于 2015-06-29 14:41:20
回复(1)
/* 01背包问题 */ #include <iostream> #include <vector> using namespace std; void Memset(int **item,int row,int column) { for(int i=0;i<row;i++) for(int j=0;j<column;j++) item[i][j]=0; } void DeletePoints(int **p,int row) { for(int i=0;i<row;i++) delete[] p[i]; } int main() { /**********将输入存入变量中****************/ int T; cin>>T; while(T--) { int n,bot,top; cin>>n>>bot>>top;//n 餐厅数量 vector<vector<int>> c,v; for(int i=0;i<n;i++) { vector<int> vectC; vectC.push_back(0); c.push_back(vectC); vector<int> vectV; vectV.push_back(0); v.push_back(vectV); } for(int j=0;j<n;j++) { int foodCount; cin>>foodCount; for(int i1=0;i1<foodCount*2;i1++) { int temp; cin>>temp; if(i1%2==0) c[j].push_back(temp); else v[j].push_back(temp); } } int nMax=0;//最大享受度 //按餐厅计算最大享受度 for(int a=0;a<c.size();a++) { int nConsume=0; vector<int> w=c[a];//食堂a中各个食物的价格 vector<int> value=v[a];//食堂a中各食物的享受度 int **enjoy=new int*[w.size()];//二维数组指针，用于存储不同花费下的最大享受度 int **fee=new int*[w.size()];//二维数组指针，用于存储最大享受度对应的费用 for(int k=0;k<w.size();k++) { int *item=new int[top+1]; enjoy[k]=item; int *itemFee=new int[top+1]; fee[k]=itemFee; } //初始化二维数组 Memset(enjoy,w.size(),top+1); Memset(fee,w.size(),top+1); /**************算法核心部分从此处开始**********/ for(int m=1;m<w.size();m++) { for(int n=1;n<=top;n++) { if(w[m]>n) { enjoy[m][n]=enjoy[m-1][n];//不选m fee[m][n]=fee[m-1][n]; } else { if(enjoy[m-1][n]>enjoy[m-1][n-w[m]]+value[m]) { enjoy[m][n]=enjoy[m-1][n];//不选m fee[m][n]=fee[m-1][n]; } else { enjoy[m][n]=enjoy[m-1][n-w[m]]+value[m];//选m fee[m][n]=fee[m-1][n-w[m]]+w[m]; } } } } //如果最大享受度对应的花费小于最小花费，则度熊不消费，享受度置为0 int nCurrMax=fee[w.size()-1][top]>=bot?enjoy[w.size()-1][top]:0; if(nCurrMax>nMax) nMax=nCurrMax; DeletePoints(enjoy,w.size()); DeletePoints(fee,w.size()); delete[] enjoy; delete[] fee; } cout<<nMax<<endl; } return 0; }
编辑于 2015-09-11 16:30:16
回复(0)
// 带你们瞻仰一下大神的代码(当然不是我写的啦~v~)
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int ans[10010];
int main()
{
int T, n, bot, top, m, c, v, i, k;
cin >> T;
while(T--)
{
cin >> n >> bot >> top;
k = 0;
while(n--)
{
memset(ans, 0, sizeof(ans));
cin >> m;
while(m--)
{
cin >> c >> v;
for(i = top; i >= c; i--)
{
if((ans[i - c] > 0) || (0 == i - c))
{
ans[i] = max(ans[i], ans[i - c] + v);
}
}
}
for(i = bot; i <= top; i++)
{
k = max(k, ans[i]);
}
}
cout << k << endl;
}
return 0;
}
发表于 2015-09-08 16:48:58
回复(0)
# 求最大享受度
defmax_xiangshoudu():
# 请输入数据组数t
t =int(input('请输入数据组数:'))
# 用来存放每组数据的最大享受度
max_xsd =[]
fori inrange(1, t+1):
data =input('请输入第%d组数据:'%i)
data_list =data.strip().split()
data_list =[int(i) fori indata_list]
n, bot, top =tuple(data_list)
temp_list =[]
forj inrange(1, n+1):
restu_data =input('请输入食堂%d的食物数和食物的(价钱,享受度):'%j)
restu_data_list =restu_data.strip().split()
restu_data_list =[int(i) fori inrestu_data_list]
temp_list.append(restu_data_list)
print('temp_list: \n', temp_list)
temp_sxd_list =[] # 用来存放每组数据中每个食堂对应的最大的享受度
fork intemp_list:
# 将每个食堂的数据变成列表嵌套元祖格式
temp_li_tuple =[]
p =1
whilep <=len(k)-2:
temp_li_tuple.append((k[p], k[p+1]))
p +=2
# 根据价格排序列表
temp_li_tuple =sorted(temp_li_tuple)
print('temp_li_tuple: \n', temp_li_tuple)
# 根据bot和top计算最大享受度
price_sum =0
xsd_sum =0
forprice, xsd intemp_li_tuple:
ifprice > top: # 避免最便宜的食物价钱超过top值
# print('您消费不起！')
break
if(price_sum +price) > top:
# print('您已经没钱了！')
break
else:
price_sum +=price
xsd_sum +=xsd
ifprice_sum < bot: # 未满足最低消费
xsd_sum =0
temp_sxd_list.append(xsd_sum)
# 从每组数据中选择出享受度最大的
temp_sxd_list.sort(reverse=True)
max_xsd.append(temp_sxd_list[0])
# 打印
forMAX_XSD inmax_xsd:
print(MAX_XSD)
# return max_xsd
if__name__ =='__main__':
max_xiangshoudu（）
发表于 2019-03-29 17:07:13
回复(0)
import java.util.*;
/*
题目中输入例子的格式跟输入的描述不太一样，应该是：
2
2 10 20
5（食堂1有五道菜）
1 1 2 1 5 1 10 1 20 1
5（食堂2有五道菜）
1 2 2 2 5 2 10 2 20 2
2 10 10
1（食堂1有一道菜）
5 1
1（食堂2有一道菜）
5 1
*/
public class Main{
private static Scanner sc=new Scanner (System.in);
public static void main(String[] args){
sc.nextLine();
while(sc.hasNext()){
int n=sc.nextInt();
int bot=sc.nextInt();
int top=sc.nextInt();
int[] s=new int[n];
for(int i=0;i<n;i++){
int m=sc.nextInt();
int[] c=new int[m+1];
int[] v=new int[m+1];
for(int j=1;j<=m;j++){
c[j]=sc.nextInt();
v[j]=sc.nextInt();
}
int[][] a=new int[m+1][top+1];
for(int j=1;j<=top;j++){
for(int k=1;k<=m;k++){
if(c[k]<=j)a[k][j]=Math.max(a[k-1][j],a[k-1][j-c[k]]+v[k]);
else a[k][j]=a[k-1][j];
}
}
if(a[m][bot-1]==a[m][top])s[i]=0;
else s[i]=a[m][top];
}
int max=Integer.MIN_VALUE;
for(int i=0;i<n;i++)max=Math.max(max,s[i]);
System.out.println(max);
}
}
}
发表于 2017-02-27 03:53:19
回复(0)
#include <iostream>#include <algorithm>#include <vector>#include <climits>using namespace std;intmain(){intT;cin >> T;while(T--){intn, bot, top;cin >> n >> bot >> top;intvSumMax = INT_MIN;for(inti = 0; i < n; i++){vector<int> dp(top + 1, 0);intmi;cin >> mi;for(intj = 0; j < mi; j++){intc, v;cin >> c >> v;//找恰好的weightfor(intweight = top; weight >= c; weight--){if(dp[weight - c] > 0|| weight - c == 0){dp[weight] = max(dp[weight], dp[weight-c] + v);}}}for(intweight = bot; weight <= top; weight++){vSumMax = max(vSumMax, dp[weight]);}}cout << vSumMax << endl;}return0;}
发表于 2016-08-30 11:28:58
回复(0)
import java.util.*;
public class Main{
public static void main(String []args){
Scanner sc=new Scanner(System.in);
int tries=sc.nextInt();
for(int i=0;i<tries;i++){
int n=sc.nextInt();
int bot=sc.nextInt();
int top=sc.nextInt();
int [][]c=new int[n][];
int [][]v=new int[n][];
for(int j=0;j<n;j++){
int type=sc.nextInt();
c[j]=new int[type];
v[j]=new int[type];
for(int k=0;k<type;k++){
c[j][k]=sc.nextInt();
v[j][k]=sc.nextInt();
}
}
// c[] v[] bot top
int max=0;
for(int j=0;j<n;j++){
int tmp=ddx(bot,top,c[j],v[j]);
if(max<tmp){
max=tmp;
}
}
System.out.println(max);
}
}
private static int ddx(int bot,int top,int []w,int []p){
// int W=0;
// for(int i=0;i<w.length;i++){
// W+=w[i];
// }
// if(W<bot){
// return 0;
// }
int [][]dp=new int[w.length+1][top+1];
for(int i=1;i<=w.length;i++){
for(int j=1;j<=top;j++){
if(j<w[i-1]){
dp[i][j]=dp[i-1][j];
}else{
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i-1]]+p[i-1]);
}
}
}
// 判断最大值
return dp[w.length][top]==dp[w.length][bot-1]?0:dp[w.length][top];
}
}
编辑于 2016-08-29 14:19:33
回复(0)
#include<iostream>
using namespace std;
#define MAXSIZE 100
typedef struct _FOOD
{
int price;
int levelofshare;
}food,FoodInHall[MAXSIZE];
typedef struct _HALL
{
FoodInHall food_in_hall;
int count;
}hall;
int main()
{
int i,j,k;
int result;
int n,bot,top;
cin>>n>>bot>>top;
hall *p_hall;
p_hall = new hall[n];
for(i=0;i<n;i++)
{
cin>>p_hall[i].count;
for(j=0;j<p_hall[i].count;j++)
cin>>p_hall[i].food_in_hall[j].price
>>p_hall[i].food_in_hall[j].levelofshare;
}
food *CostAndEnjoy=new food[n];
for(i=0;i<n;i++)
{
CostAndEnjoy[i].levelofshare=0;
CostAndEnjoy[i].price = 0;
}
food min;min.levelofshare=0;min.price=0;
for(i=0;i<n;i++)
{
for(j=0;j<p_hall[i].count;j++)
{
if((CostAndEnjoy[i].price+p_hall[i].food_in_hall[j].price)<top)
{
CostAndEnjoy[i].price += p_hall[i].food_in_hall[j].price;
CostAndEnjoy[i].levelofshare += p_hall[i].food_in_hall[j].levelofshare;
}
else
{
min=p_hall[i].food_in_hall[j];
for(k=1;k<j;k++)
{
if(p_hall[i].food_in_hall[k].price>=min.price&&p_hall[i].food_in_hall[k].levelofshare<=min.levelofshare)
min=p_hall[i].food_in_hall[k];
}
if(min.levelofshare!=p_hall[i].food_in_hall[j].levelofshare||min.price!=p_hall[i].food_in_hall[j].price)
{
CostAndEnjoy[i].price = CostAndEnjoy[i].price-min.price
+p_hall[i].food_in_hall[j].price;
CostAndEnjoy[i].levelofshare=CostAndEnjoy[i].levelofshare-min.levelofshare
+p_hall[i].food_in_hall[j].levelofshare;
}
}
}
}
food maxEnjoy=CostAndEnjoy[0];
for(i=1;i<n;i++)
{
if(CostAndEnjoy[i].price<=top&&CostAndEnjoy[i].levelofshare>=maxEnjoy.levelofshare)
maxEnjoy=CostAndEnjoy[i];
}
if(maxEnjoy.price<bot||maxEnjoy.price>top)
result=0;
else
result=maxEnjoy.levelofshare;
delete [] p_hall;
delete [] CostAndEnjoy;
cout<<result<<endl;
return 0;
}
发表于 2015-09-16 11:12:22
回复(1)
关于DP的处女座，花了近两个小时啊，唉…… package com.looking_for_job; import java.util.Scanner; import java.util.SortedMap; import java.util.TreeMap; /** * 加班了一个通宵的度度熊，神经有点恍惚，想到依然未能解决的Bug，眼泪禁不住霹雳哗啦往下掉……他抬头看了看帝都灰蒙蒙的天空，一咬牙，一跺脚，大叫一声——劳资今天要吃点好的！ 已知本厂有n个食堂，第i（i属于[1,n])个食堂有m[i]种食物，每种食物有一个价钱c，享受度v，度度熊希望去一个食堂就餐，花费[bot,top]范围内的钱数（也可以拍桌子走人，哪里都不吃了），选择若干种食物，使得自己所能获得的享受度最大。（注意，度度熊还有一个挑食的特点，同一种食物他最多只会点一份。） 现在告诉你所有食堂食物的信息，希望你进行选择搭配，使得度度熊可以得到最大的享受度，并输出这个享受度的值。 输入描述: 第一行是一个正整数T（1<=T<=20),表示有T组测试数据。 对于每组数据—— 第一行是三个数n，bot，top，n代表食堂数1<=n<=10），bot是这次吃饭的最低消费，top是这次吃饭的最高消费（0<=bot，top<=10000） 接下来依次是n个食堂的信息，对于第i个食堂 第一行是一个数m[i]（o<=m[i]<=100)，代表第i个食堂的食物数 第二行有2*m[i]个数，分别是c[i][1]，v[i][1]，c[i][2]，v[i][2]，……c[i][m[i]]，v[i][m[i]] c[i][j]表示第i个餐厅第j种食物的价钱，v[i][j]代表第i个餐厅第j种食物给度度熊带来的享受度。 输出描述: 对于每组数据，请输出一行，每行一个正整数。表示度度熊所能获得的最大享受度。 数据结果保证不会超过2^31-1. 输入例子: 2 2 10 20 5 1 1 2 1 5 1 10 1 20 1 5 1 2 2 2 5 2 10 2 20 2 2 10 10 1 5 1 1 5 1 输出例子: 8 0 * @author zhangshaoliang * 2015-9-11 下午3:46:55 */ public class Test_dp { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub getValue(); /**int[] c = {1,2,5,10,20}; int[] v = {2,2,2,2,2}; System.out.println(dp(10, 20, c, v)); */ } /** * * @param n n个食堂 * @param bot 最小消费 * @param top 最大消费 * @param m 食堂里的事物数组 * @param c 价格 * @param v 价值 * @return */ public static void getValue(){ Scanner scan = new Scanner(System.in); int T = Integer.valueOf(scan.nextLine());////组数 while(T>0){ String[] str =scan.nextLine().split("\\s"); int n = Integer.valueOf(str[0]); int bot = Integer.valueOf(str[1]); int top = Integer.valueOf(str[2]); ////用排序map保存每个食堂的最大享受度 SortedMap<Integer,Integer> map = new TreeMap<Integer, Integer>();///存储每个食堂的最大价值 while(n>0){////输入每个食堂的数据 String[] data =scan.nextLine().split("\\s"); int[] c = new int[Integer.valueOf(data[0])]; int[] v = new int[Integer.valueOf(data[0])]; for(int i=0;i<c.length;i++){ c[i] = Integer.valueOf(data[2*i+1]); v[i] = Integer.valueOf(data[2*(i+1)]); } int value = dp(bot, top, c, v);////计算每个食堂最大的享受度 map.put(value, value); n--; } ////输出该组数据，所有食堂中，最大的享受度 System.out.println(map.get(map.lastKey())); T--; } } /** * 动态规划获取单组数据的最大价值 * @param bot * @param top * @param c * @param v * @return */ public static int dp(int bot,int top,int[] c, int[] v){ int max = 0; int[][] dp = new int[c.length][top];/////dp[i][j]表示在最高花费为j情况下，购买前i个事物所取得的最大值 int[][] price = new int[c.length][top];////每一种选择情况对应的消费金额 for(int i=0;i<c.length;i++) { dp[i][0] = 0;////最高花费为0元时取得的价值 } for(int j=0;j<top;j++){ dp[0][j] = 0;/////购买0个事物取得的价值 } for(int i=0;i<c.length;i++){ for(int j=0;j<top;j++){ if(c[i]>j){ dp[i][j] = i==0? 0 : dp[i-1][j]; ////第i个事物太贵，不能购买 price[i][j] = i==0? 0 : price[i-1][j];////跟前i-1消费一样 }else{ dp[i][j] = i==0 ? v[i] : Math.max(dp[i-1][j], dp[i-1][j-c[i]]+v[i]);////买下该食物 price[i][j] = i==0 ? c[i] : Math.max(price[i-1][j], price[i-1][j-c[i]]+c[i]);////花费 } max = dp[i][j]>max? dp[i][j] : max; } } ////判断最低消费是否在合理区间内 if(price[c.length-1][top-1]>=bot){ return dp[c.length-1][top-1]; }else{ return 0; } } }
编辑于 2015-09-11 17:19:13
回复(0)
// 我的代码为什么会出现段错误，用dp做的，测试用例可以过 求好心人看看
#include<iostream> #include<algorithm> #include<vector> using namespace std;
int main()
{
int n, bot, top;
int T; cin>>T;
int buffer_size = 0;
int res; vector<int> dp;
vector<int> rdp;
vector<int> c,v;
for(int i = 0; i < T; i++){
cin>>n>>bot>>top;
res = 0; int temp = 0;
for(int j = 0; j < n; j++){
int m; cin>>m;
if(m == 0) {
res = 0; continue;
}
if(buffer_size<n){
v.resize(m,0);
c.resize(m,0);
buffer_size = m;
}
for(int k = 0; k < m; k++){
cin>>c[k]; cin>>v[k];
}
dp.resize(top+1,0);
bool flag = 0;
for( int w = 1; w <= top; w++){
if(w >= c[0]){
dp[w] = v[0];
}else
dp[w] = 0;
}
res = (top >= c[0] && c[0] > bot) ? v[0] : 0;
for(int k = 1; k < m; k++){
rdp = dp;
for( int w = 1; w <= top; w++){
if(w - c[k] >= 0){
temp = rdp[w-c[k]] + v[k];
}
dp[w] = max(temp, rdp[w]);
if(w >= bot && w<=top)
res = max(res, dp[w]);
}
rdp = dp;
}
} cout<<res<<endl; } return 0; }
编辑于 2015-09-08 15:09:30
回复(0)
问题信息
通过挑战的用户
-
2021-04-09 14:53:29 -
2021-04-05 21:26:13 -
2021-03-21 05:26:35 -
2021-03-16 17:24:08 -
2021-03-09 13:51:51
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
