乘船问题（2人与多人）O(n)

问题描述：有n个人，第i个人的重量是wi，每艘船的最大载重均为m，且最多容纳两个人，用最少的船装载所有人

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int dp[100];
int w[100],v[100];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>w[i];
    int i=0,j=n-1,res=0;
    while(i<=j){
        if(i==j){
            res++;
            break;
        }
        else if(w[i]+w[j]>m){
            j--;
            res++;
        }
        else{
            res++;
            j--;
            i++;
        }
    }
    cout<<res<<endl;
    return 0;
}

问题描述：有n个人，第i个人的重量是wi。每艘船的最大载重均为m，人数不限，用最少的船装载所有人

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int dp[100];
int w[100],v[100];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>w[i];
    int i=0,j=n-1,res=0;
    while(i<=j){
        if(i==j){
            res++;
            break;
        }
        else if(w[i]+w[j]>m){
            j--;res++;
        }
        else{
            int k=j-1,ans=w[i]+w[j];
            while(ans+w[k]<=m&&k>i){
                ans+=w[k--];
            }
            j=k;i++;
            res++;
        }
    }
    cout<<res<<endl;
    return 0;
}