hdu 01リュックサックまとめ(1171+2546+1864+2955...

7373 ワード

1171
题意は比较的に简単で、この问题の比较的に特别な地方は01リュックサックの中で、すべての物体は1つの価値があって1つの重さがあって、比较的に価値が最大で、重さは制限されて、この问题は価値が制限されている情况の下で最大で、同じく値は01リュックサックの中の重さを価値に変えます.
//Problem : 1171 ( Big Event in HDU )     Judge Status : Accepted



#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>



using namespace std;



int v[6000], dp[5000 * 50 + 10];





int main() {

    //freopen("in.txt", "r", stdin);

    int n;

    int sum;

    while (scanf("%d", &n) != EOF && n >= 0) {

        memset(dp, 0, sizeof(dp));

        int a, b;

        sum = 0;

        int idx = 0;

        for (int i = 1; i <= n; i++) {

            scanf("%d%d", &a, &b);

            sum += a * b;

            for (int j = 0; j < b; j++) {

                v[++idx] = a;

            }

        }

        for (int i = 1; i <= idx; i++)

            for (int j = sum / 2; j >= v[i]; j--)

                dp[j] = max(dp[j], dp[j - v[i]] + v[i]);

        printf("%d %d
", sum - dp[sum / 2], dp[sum / 2]); } return 0; }

2546
上と同じように、重さがなく、価値しかありません.
カードに5元未満の場合は、元の値を出力します.5元より大きい場合は、m-5の範囲で最も多くのお金(最も高い料理を残す)を使って、残りのお金で最も高い料理を減らします.
コード#コード#
//Problem : 2546 (    )     Judge Status : Accepted

#include <iostream>

#include <algorithm>

using namespace std;



int v[1005];

int dp[1005];



int main()

{

    int n, m;

    while (cin >> n && n) {

        memset(dp, 0, sizeof(dp)); //        wa   。。。

        for (int i = 1; i <= n; ++i) {

            cin >> v[i];

        }

        cin >> m;

        if (m < 5) {

            printf("%d
", m); continue; } sort(v + 1, v + n + 1); for (int i = 1; i < n; ++i) { for (int j = m - 5; j >= v[i]; j--) dp[j] = max(dp[j], dp[j - v[i]] + v[i]); } printf("%d
", m - dp[m - 5] - v[n]); } return 0; }

2602
水問題、書きません.基本01リュックサック.
1864
題意は簡単で、作り方も簡単で、すべて*100が整数になって01リュックサックになります.
一箇所(int)(q*100)うっかり書きました(int)q*100は長い間デバッグしてやっと見つけました、バカ==
//Problem : 1864 (       )     Judge Status : Accepted



/**<  hdu 1864 */

#include <iostream>

#include <cstdio>

#include <algorithm>



using namespace std;



double pri[35];     //       

int pric[35];

int dp[35 * 1000 * 100];



int main()

{

    double q;

    int n, m;

    double pri_a, pri_b, pri_c;

    while (scanf("%lf%d", &q, &n) != EOF && n) {

        int idx = 0;

        for (int i = 0; i < n; ++i) {

            cin >> m;

            pri_a = pri_b = pri_c = 0;

            char ch;

            double price;

            int ok = 1;

            for (int j = 0; j < m; ++j) {

                scanf(" %c:%lf", &ch, &price);

                switch(ch) {

                case 'A' :

                    pri_a += price;

                    break;

                case 'B' :

                    pri_b += price;

                    break;

                case 'C' :

                    pri_c += price;

                    break;

                default: ok = 0;

                }

            }

            double sum = pri_a + pri_b + pri_c;

            //printf("a=%f,b=%f,c=%f,sum=%f
", pri_a, pri_b, pri_c, sum); if (!(pri_a > 600 || pri_b > 600 || pri_c > 600 || sum > 1000) && ok) pri[++idx] = sum; } //end for pri[] for (int i = 1; i <= idx; i++) { pric[i] = (int)(pri[i] * 100); } memset(dp, 0, sizeof(dp)); for (int i = 1; i <= idx; ++i) { for (int j = (int)(q * 100); j >= pric[i]; --j) { dp[j] = max( dp[j], dp[j - pric[i]] + pric[i]); } } printf("%.2f
", dp[(int)(q * 100)] / 100.00); } return 0; }

この問題も別の方法で作ることができて、枚数でリュックサックになります.
私たちの普段のリュックサックは品質で、データが大きすぎるとき、あるいはこれのように実数で、思考を転換することができて、価値でリュックサックなどになります.
//Problem : 1864 (       )     Judge Status : Accepted



#include <iostream>

#include <cstdio>

#include <algorithm>



using namespace std;



double pri[35];

double dp[35];



int main()

{

    double q;

    int n, m;

    double pri_a, pri_b, pri_c;

    while (scanf("%lf%d", &q, &n) != EOF && n) {

        int idx = 0;

        for (int i = 0; i < n; ++i) {

            cin >> m;

            pri_a = pri_b = pri_c = 0;

            char ch;

            double price;

            int ok = 1;

            for (int j = 0; j < m; ++j) {

                scanf(" %c:%lf", &ch, &price);

                switch(ch) {

                case 'A' :

                    pri_a += price;

                    break;

                case 'B' :

                    pri_b += price;

                    break;

                case 'C' :

                    pri_c += price;

                    break;

                default: ok = 0;

                }

            }

            double sum = pri_a + pri_b + pri_c;

            //printf("a=%f,b=%f,c=%f,sum=%f
", pri_a, pri_b, pri_c, sum); if (!(pri_a > 600 || pri_b > 600 || pri_c > 600 || sum > 1000) && ok) pri[++idx] = sum; } //end for pri[] for (int i = 0; i <= idx; i++) { dp[i] = 0.0; } for (int i = 1; i <= idx; ++i) { for (int j = idx; j >= 1; --j) { if (dp[j - 1] + pri[i] <= q) dp[j] = max(dp[j], dp[j - 1] + pri[i]); } } double ans = 0; for (int i = 1; i <= idx; ++i) if (ans < dp[i]) ans = dp[i]; printf("%.2f
", ans); } return 0; }

2955
また整数ではない問題で、この問題は前のように簡単にx 100で完成できないことがわかります.精度が足りないからです.
確率をリュックサックにすることができて、この問題はもう1か所異なってプラスするかどうか、確率は乗るのです
//Problem : 2955 ( Robberies )     Judge Status : Accepted



#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;



double P[105];  //           

int M[105];     //         ...

double dp[10005];



int main()

{

    int t;

    cin >> t;

    while (t--) {

        int n;

        int sum = 0;

        double p;

        cin >> p >> n;

        for (int i = 1; i <= n; ++i) {

            cin >> M[i] >> P[i];

            P[i] = 1 - P[i];

            sum += M[i];

        }

        memset(dp, 0, sizeof(dp));//       wa  。。。

        dp[0] = 1;  //         1

        for (int i = 1; i <= n; ++i) {

            for (int j = sum; j >= M[i]; --j) {

                dp[j] = max(dp[j], dp[j - M[i]] * P[i]); //        

            }

        }

        for (int i = sum; i >= 0; --i)

            if (dp[i] > 1 - p) {

                printf("%d
", i); break; } } return 0; }