第一行是一个正整数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<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; }
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]; } }
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; } } }
#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; }
#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维的。
#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; }
/* 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; }
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);
}
}
}
#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;}
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]; } }
#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;
}
关于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; } } }
// 带你们瞻仰一下大神的代码(当然不是我写的啦~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; }
// 我的代码为什么会出现段错误,用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; }