完全背包問題

完全背包就是每件物品都有無限多個可以放到背包裡
比較前面的0-1背包問題其實程式實作只差一行
因為0-1背包問題只能放置一個東西，所以我們必須從後面推回來（從m算到need[i]）原因是後面與前面無關，問題是仰賴前面的解來作解

但在完全背包問題中，因為每件物品可以一直放，所以呀~要從前面算到後面（從need[i]算到m)這樣只要背包空間足夠就可以再放同一件物品進去（較大的容量是depend在較小的容量上，此時較小容量也許已經放了第i項物品，但算到較大時仍可再放）

AC程式碼 (http://hihocoder.com/problemset/problem/1043)

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <cstring>

using namespace std;

int main()

{

    int n,m;

    while(cin >> n >> m)

    {

        int dp[100005],value[505],need[505];

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

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

        {

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

        }

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

        {

            for(int j=need[i];j<=m;j++)

            {

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

            }

        }

        cout << dp[m] << endl;

    }

    return 0;

}