題干：

The Problem

Mack, in an effort to avoid being cracked, has enlisted your advice as to the order in which turtles should be dispatched to form Yertle's throne. Each of the five thousand, six hundred and seven turtles ordered by Yertle has a different weight and strength. Your task is to build the largest stack of turtles possible.

Input

Standard input consists of several lines, each containing a pair of integers separated by one or more space characters, specifying the weight and strength of a turtle. The weight of the turtle is in grams. The strength, also in grams, is the turtle's overall carrying capacity, including its own weight. That is, a turtle weighing 300g with a strength of 1000g could carry 700g of turtles on its back. There are at most 5,607 turtles.

Output

Your output is a single integer indicating the maximum number of turtles that can be stacked without exceeding the strength of any one.

Sample Input

300 1000 1000 1200 200 600 100 101

Sample Output

3

?

題目大意：

給出n只烏龜（n<=6000）的體重和可以承受的重量。?求可以疊起來(lái)的最高的烏龜是多少。

解題報(bào)告：

? 類似一個(gè)0-1背包，只不過(guò)他把真正的權(quán)值放在了第二維上，反而把原本的第二維放在了權(quán)值上，這樣我們需要權(quán)值的時(shí)候就倒著判斷一遍就好了。或者直接記錄可以到達(dá)的最大值然后輸出就行了。

?

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; const int INF = 0x3f3f3f3f; struct Node {int w,p;//w體重，p承重 } node[MAX]; bool cmp(Node a,Node b) {if(a.p!=b.p) return a.p<b.p;else return a.w < b.w; //貌似可以不加 } int tot; int dp[MAX]; int main() {int q,qq;while(~scanf("%d%d",&q,&qq)) {node[++tot].w=q;node[tot].p=qq;}sort(node+1,node+tot+1,cmp);memset(dp,INF,sizeof dp);dp[0]=0;int maxx = 0;for(int i = 1; i<=tot; i++) {for(int j = maxx+1;j>=0; j--) {if(node[i].p > dp[j-1]+node[i].w) {dp[j] = min(dp[j],dp[j-1]+node[i].w);maxx = max(maxx,j);}}}printf("%d\n",maxx);return 0 ;}

二維去寫：

一篇

另一篇

大概貼一個(gè)代碼過(guò)來(lái)、

#include <cstdio> #include <algorithm> #include <vector> #include <map> #include <queue> #include <iostream> #include <stack> #include <set> #include <cstring> #include <stdlib.h> #include <cmath> using namespace std; typedef long long LL; typedef pair<int, int> P; const int INF = 1000000000; const int maxn = 10000 + 5;struct Node{int first, second;Node(int f=0, int s=0){this -> first = f;this -> second = s;} }t[maxn];bool cmp(Node a, Node b){return a.first+a.second < b.first+b.second; }int dp[maxn][maxn];int main(){int w, c;int n = 0;while(scanf("%d%d", &w, &c) != EOF){t[n++] = Node(w, c-w);}sort(t, t+n, cmp);for(int i = 0;i < n;i++){fill(dp[i], dp[i]+maxn, INF);dp[i][0] = 0;}dp[0][1] = t[0].first;for(int i = 1;i < n;i++){for(int j = 1;j <= n;j++){dp[i][j] = dp[i-1][j];if(t[i].second >= dp[i-1][j-1]){dp[i][j] = min(dp[i][j], dp[i-1][j-1]+t[i].first);}}}int ans = 0;for(int i = n;i >= 0;i--){if(dp[n-1][i] != INF){ans = i;break;}}printf("%d\n", ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【UVA - 10154 】Weights and Measures （贪心排序，dp,类似0-1背包，状态设定思维）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。