题目:

有重量分别为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;
}