779      阿裏雲  技術社區[雲棲]

WIKIOI-1014 裝箱問題

有一個箱子容量為V（正整數，0＜＝V＜＝20000），同時有n個物品（0＜n＜＝30），每個物品有一個體積（正整數）。

要求n個物品中，任取若幹個裝入箱內，使箱子的剩餘空間為最小。

一個整數v，表示箱子容量

一個整數n，表示有n個物品

接下來n個整數，分別表示這n 個物品的各自體積

一個整數，表示箱子剩餘空間。

24

6

8

3

12

7

9

7

0

 

 

思路：

經典的01背包問題，看代碼吧

#include<stdio.h>
int w[20010];
int dp[20010],Weight;
int max(int a,int b)
{return a>b?a:b;}
int zeroOnePack(int n)//01背包
{
    for(int i=1; i<=n; i++)
    {
        for(int j=Weight; j>=w[i]; j--)
        {
            dp[j] = max(dp[j], w[i] + dp[j-w[i]]);
        }
    }
    return dp[Weight];
}
int main()
{
    int i,j,n;
    scanf("%d%d",&Weight,&n);
    for(i=1;i<=n;i++)
    scanf("%d",&w[i]);
    printf("%d\n",Weight-zeroOnePack(n));
    return 0;
} 

 

最後更新：2017-04-03 12:55:33

  上一篇： 怎麼讓有些QQ好友的動態不在自己空間裏顯示

  下一篇： linux rpm 卸載，簡單說明