01背包問題

Pleiades_Antares

打個模板，基本上01背包都這個樣子了～

從百度上摘來兩張圖，簡單可以說明01背包了應該

這是我找的第一張

這是我找的第二張

01背包是DP的內容，DP剛開始學一般都是記憶化搜索嘛，那就是優化過的搜索問題

不知道這麼說各位能不能理解“記憶化搜索”這個名字qwq

如果需要的更詳細的解釋的話麻煩評論下/站內信，我把具體的內容再發出來

（quq我都有課件闊是我懶得再搬運PPT了qwq需要的話再發出來咯）

（至於我為什麼最近不寫TG相關只寫最基礎的PJ的內容，請戳這裡瞭解）

代碼放出來：

//01背包 
#include<iostream>
using namespace std;
//stellar myself！
const int maxn=1000;
int m[maxn][maxn];
int w[maxn],v[maxn];
int C,N;
void add(int i,int j){
    if (j<w[i])
        m[i][j]=m[i-1][j];
    else
        m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
}
int main(){
    cin>>N>>C;
    for(int i=1;i<=N;i++){
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=C;j++){
            add(i,j);
        }
    }
    int big=m[1][1];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=C;j++){
            if (m[i][j]>big) big=m[i][j];
        }
    }
    cout<<big<<endl;
    return 0;
} 

如有疏漏還請指出