最少数量货物装箱问题

题目：

有重量分别为3，5，7公斤的三种货物，和一个载重量为X公斤的箱子
（不考虑体积等其它因素，只计算重量）
需要向箱子内装满X公斤的货物，要求使用的货物个数尽可能少（三种货物数量无限）

解析：

对7取余，对余数进行讨论即可
余数为1,3,5，则可以装满，1可以视为1+7=3+5，是之前的count+1
余数为2,4,6，也可以装满，2可以视为2+7=3+3+3，4可以视为4+7=5+3+3，6=3+3是之前的count+2

代码：

• 普通法：

int main()
{


    int x;
    cin>>x;
    int count = 0;

    if(x==1 || x==2 || x==4)
        cout<<-1;
    else{
        count = x/7;
        int n = x%7;
        if(n==1 || n==3|| n==5){
            count +=1;
        }
        else if(n==2||n==4||n==6){
            count +=2;
        }
        cout<<count;
    }


    return 0;
}

• 动态规划

#include<iostream>
#include<vector>
#define MAX 10000
using namespace std;
int min(int a,int b){
    return a<b?a:b;
}
int main(){
    int X;
    cin>>X;
    vector<int> dp(X+1,MAX);
    dp[3]=1;
    dp[5]=1;
    dp[6]=2;
    dp[7]=1;
    for(int sum=8;sum<=X;sum++){
//装8 可以看作5装3 3装5 1装7 这三个策略演变过来取最小的+1
        dp[sum]=min(dp[sum-3],min(dp[sum-5],dp[sum-7]))+1;
    }
    cout<<(dp[X]>=MAX?-1:dp[X])<<endl;
    return 0;
}