九度OJ 1152:注文問題(01リュック、DP)

時間制限:1秒
メモリ制限:32メガ
特殊問題:いいえ
コミット:1046
解決:543
タイトルの説明:
北京大学のネットの実験室はいつも活动があって外で买う必要があって、しかし毎回外で买う清算の経费の総额は最大でC元で、N种类の野菜があって注文することができて、长い时间の注文を経て、ネットの実験室はすべての野菜iに対してすべて1つの量子化の評価点数(この野菜のおいしい程度を表します)があって、Viで、すべての野菜の価格はPiで、どのように各種の野菜を選んで、清算額の範囲内で注文する野菜の総評価点数を最大にすることができます.注意:栄養の多様化が必要なため、すべての野菜は一回しか注文できません.
入力:
入力された最初の行には、2つの整数C(1<=C<=1000)とN(1<=N<=100)があり、Cは合計で清算可能な額を表し、N>は注文可能な数を表す.次のN行は、1から100の間(1と100を含む)の2つの整数を含み、それぞれ料理の>価格と料理の評価点数を表す.
出力:
出力は1行のみで、この行には整数が1つしか含まれておらず、清算額の範囲内で注文した料理の最大評価点数を表しています.
サンプル入力:

90 4
20 25
30 20
40 50
10 18
40 2
25 30
10 8

サンプル出力:

95
38

ソース:
2010年北京大学コンピュータ研究生気試験の本題
考え方:
典型的な01バックパックの問題では、1次元配列DPはメモリを低減することができる.
コード:

#include <stdio.h>
#include <string.h>
 
#define N 100
#define C 1000
 
int main(void)
{
    int c, n, i, j;
    int price[N], score[N];
    int dp[C+1];
 
    while (scanf("%d%d", &c, &n) != EOF)
    {
        for (i=0; i<n; i++)
            scanf("%d%d", &price[i], &score[i]);
 
        memset(dp, 0, sizeof(dp));
        for (i=0; i<n; i++)
        {
            for (j=c; j>=price[i]; j--)
            {
                int tmp = dp[j-price[i]] + score[i];
                dp[j] = (tmp > dp[j]) ? tmp : dp[j];
            }
        }
        printf("%d
", dp[c]);
    }
 
    return 0;
}
/**************************************************************
    Problem: 1152
    User: liangrx06
    Language: C
    Result: Accepted
    Time:10 ms
    Memory:912 kb
****************************************************************/