题解 | #点菜问题#

0-1 背包问题
dp方程 dp[i][j] = max(dp[i-1][j] (不放入),dp[i-1][j-w[i]]+V[i] (放入))
由于至于上一行有关可以简化
dp[j] = max(dp[j],dp[j-W[i]])
坑点:注意循环写法
for(int i=0;i<N;i++)
  for(int j = C;j>=W[i];j--)

#include<iostream>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    int C,N;
    while(cin>>C&&cin>>N){
        int V[N];int W[N];
        for(int i =0;i<N;i++){
            cin>>W[i]>>V[i];
        }
        int dp[C+1];
        memset(dp,0,sizeof(dp));
        for(int i=0;i<N;i++){
           for(int j=C;j>=W[i];j--){
               dp[j] = max(dp[j],dp[j-W[i]]+V[i]);
           }
        }
        cout<<dp[C]<<"\n";
    }
    
}