uva 10154 Weights and Meassis

n匹の亀の体重と耐えられる重さを与えて、自分の体重も耐えて、亀達を畳み上げて、どれぐらいの高さまで積み重ねることができますか?
変形した01のリュックサックです.まず亀を力順に並べてから、01のリュックサックを作ります.
コード:

  /* * Author: illuz <iilluzen[at]gmail.com> * Blog: http://blog.csdn.net/hcbbt * File: uva10154.cpp * Create Date: 2013-11-09 11:13:55 * Descripton: dp */  

    #include <cstdio> 
    #include <algorithm> 
    using namespace std;  

    const int MAXN = 6000;  
    const int MAX = 0x7ffffff;  

    struct Turtle {  
        int wei, stg;  
    } t[MAXN];  

    int w, s, n, dp[MAXN];  

    bool cmp(const Turtle &a, const Turtle &b) {  
        if (a.stg != b.stg)  
            return a.stg < b.stg;  
        return a.wei < b.wei;  
    }  

    int main() {  
        while (scanf("%d%d", &w, &s) != EOF)  
            if (s >= w)  
                t[++n].wei = w, t[n].stg = s;  

        sort(t + 1, t + n + 1, cmp);  
        for (int i = 1; i <= n; i++)  
            dp[i] = MAX;  

        int ans = (n ? 1 : 0);  
        for (int i = 1; i <= n; i++)  
            for (int j = n; j >= 1; j--) {  
                if (t[i].stg >= dp[j - 1] + t[i].wei)  
                    dp[j] = min(dp[j], dp[j - 1] + t[i].wei);  
                if (dp[j] < MAX)  
                    ans = max(ans, j);  
            }  

        printf("%d
", ans);  

        return 0;  
    }  

この問題は偏っていましたが、最後に何回も提出しましたが、他の人の問題を見たことがありません.私の考えは複雑すぎます.原文:http://blog.csdn.net/hcbbt/article/details/14645245 ここdp[i]は現在の亀が積み込む最小重量を表していますが、実際には1次元dp[i][j]があるはずです.これはi番目の亀が高さjに積み重なった時の最小重量を表しています.順序付けされているので、記録されるjの最大値はその答えです.