0-1 背包問題

在0-1背包問題中，所有物品只有選與不選兩種選擇
因此動態方程式可以寫成
best(N,M) = max{best(N-1,M-need(N))+value(N),best(N-1,M)}

其中，value是物品價值、need可看成物品重量、N為物品個數、M為背包容量
best(N-1,M-need(N))+value(N)：選擇放入第N個物品
best(N-1,M)：不放第N個物品

為了節省空間，我們可以再將式子簡化成一維陣列實作
AC程式碼 (http://hihocoder.com/problemset/problem/1038)

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <iostream>

#include <cstring>

using namespace std;

int main()

{

    int n,m;

    while(cin >> n >> m)

    {

        int value[505],need[505];

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

        {

            cin >> need[i] >> value[i];

        }

        int dp[100005];

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

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

        {

            for(int j=m;j>=need[i];j--)

            {

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

            }

        }

        cout << dp[m] << endl;

    }

    return 0;

}