【算法】動态規劃：0-1背包問題

#include <iostream>
#include <algorithm> 
using namespace std;

int KnapSack(int w[], int v[], int n, int C)
{
    int V[n+1][C+1];

    for(int i = 0; i <= n; i++)
    {
        V[i][0] = 0;
    }
    for(int j = 0; j <= C; j++)
    {
        V[0][j] = 0;
    }
    //計算第i行，進行第i次疊代
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= C; j++)
        {
            if(j < w[i])
                V[i][j] = V[i-1][j];
            else
                V[i][j] = max(V[i-1][j], V[i-1][j-w[i]]+v[i]);
        }
    }
    //裝入的物品
    int x[n];
    int j = C;
    cout<<"裝入的物品:";
    for(int i = n ; i >= 0; i--)
    {
        if(V[i][j] > V[i-1][j])
        {
            x[i] = 1;
            j = j - w[i];
        }
        else
            x[i] = 0;
    }
    for (int i = 1; i <= n; i++){
        cout << x[i] << ' ';
	}
    cout<<endl;
    return V[n][C];
}
int main()
{
    int n;
    int C;
    
    cout<<"輸入物品的個數：";
    cin>>n;
    cout<<"輸入背包的容量：";
    cin>>C; 
    
    int v[n];
    int w[n];
    for(int i = 1 ; i <= n ; i++ )
    {
        cout << "輸入第" << i << "個物品的品質：";
        cin >> w[i];
    }
    for(int  i = 1; i <= n; i++)
    {
        cout << "輸入第" << i <<"個物品的價值：";
        cin >> v[i];
    }
    
    cout << "背包中最大價值：" << KnapSack(w, v, n, C)<<endl;
}