最省納智捷1年新車83萬起工程師靠存股年領百萬股息攝影界美人正妹指定相機款療傷止痛,王郁琦先下台!
2011-06-14 20:49:45 人氣(207) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

d862. NOIP2001 4.装箱问题

0
收藏
0
推薦

http://zerojudge.tw/ShowProblem?problemid=d862

內容 :

有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0n<=30=,每个物品有一个体积(正整数)。要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

輸入說明 :

第一行一个整数,表示箱子容量;
第二行一个整数,表示有n个物品;
接下来n行,分别表示这n 个物品的各自体积。

輸出說明 :

一个整数,表示箱子剩余空间。

範例輸入 :

24
6
8
3
12
7
9
7

範例輸出 :

0

提示 :

出處 :

NOIP2001普及组第四题 (管理:liouzhou_101)



作法 : DP
0/1 背包問題

/**********************************************************************************/
/*  Problem: d862 "NOIP2001 4.装箱问题" from NOIP2001普及组第四题       */
/*  Language: C                                                                   */
/*  Result: AC (2ms, 338KB) on ZeroJudge                                          */
/*  Author: morris1028 at 2011-06-11 09:46:59                                     */
/**********************************************************************************/


#include<stdio.h>
main() {
    int V, n, x;
    while(scanf("%d %d", &V, &n) == 2) {
        int DP[20001] = {}, a, max = 0;
        while(n--) {
            scanf("%d", &x);
            for(a = V-x; a >= 0; a--)
                if(DP[a+x] <= DP[a] + x)
                    DP[a+x] = DP[a] + x;
        }
        for(a = 0; a <= V; a++)
            max = (max > DP[a]) ? max : DP[a];
        printf("%d\n", V-max);
    }
    return 0;
}

d862NOIP2001 4.装箱问题
台長:Morris
人氣(207) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:d868. NOIP2000 1.计算器的改良
此分類上一篇:d854. NOIP2001 1.一元三次方程求解

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文