T1267-01背包问题

解题思路:

滚动数组—— 一维dp数组

遍历：

for(      )  物品

    for( 逆序） 背包

递推公式：

 dp[ j ] = max( dp[ j ] , dp[ j -w[ i ] ] + c[ i ])

 
注意事项:

参考代码:

#include <bits/stdc++.h>

using namespace std;

int main()

{

    int m,n;

    int i,j;

    cin>>m>>n;

    vector<int> w(n+1),c(n+1);

    for(i=1;i<=n;i++){

        cin>>w[i]>>c[i];

    }

    vector<int>dp(m+1,0);

    for(i=1;i<=n;i++){  

        for(j=m;j>=w[i];j--){

            dp[j]=max(dp[j],dp[j-w[i]]+c[i]);

        }

    }

    cout<<dp[m];

    return 0;

}