首页 > 试题广场 >

最少数量货物装箱问题

[编程题]最少数量货物装箱问题
  • 热度指数：8967 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
有重量分别为 3，5，7 公斤的三种货物，和一个载重量为 X 公斤的箱子（不考虑体积等其它因素，只计算重量）
需要向箱子内装满X公斤的货物，要求使用的货物个数尽可能少（三种货物数量无限）

数据范围：

输入描述:
输入箱子载重量(一个整数)。


输出描述:
如果无法装满，输出 -1。
如果可以装满，输出使用货物的总个数。
示例1

输入

4

输出

-1

说明

无法装满
示例2

输入

8

输出

2

说明

使用1个5公斤，1个3公斤货物
算法知识视频讲解
添加回答
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int x;
    cin>>x;
    vector<int> dp(x+1, INT_MAX);
    dp[3] = dp[5] = dp[7] = 1;
    dp[6] = 2;
    for(int i=8;i<=x;i++){
        if(dp[i-3]==INT_MAX && dp[i-5]==INT_MAX && dp[i-7]==INT_MAX)
            dp[i] = INT_MAX;
        else
            dp[i] = min(min(dp[i-3],dp[i-5]), dp[i-7]) + 1;
    }
    cout<<((dp[x]!=INT_MAX)?dp[x]:-1)<<endl;
    return 0;
}

发表于 2019-11-28 07:31:20 回复(0)
C/C++
昔遥暮云头像 昔遥暮云 
//动态规划背包问题
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,num[3]={3,5,7};
    cin>>n;
    vector<int> dp(n+1,9999);
    for(int j=0;j<=n;j++)
        if(j%num[0]==0)
            dp[j]=j/num[0];
    for(int i=1;i<3;i++)
        for(int j=0;j<=n;j++)
            if(j>=num[i])
                dp[j]=min(dp[j-num[i]]+1,dp[j]);
    if(dp[n]==9999)
        cout<<-1;
    else
        cout<<dp[n];
    return 0;
}

发表于 2019-10-09 10:08:36 回复(0)
earthSaver头像 earthSaver 
#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++){
        dp[sum]=min(dp[sum-3],min(dp[sum-5],dp[sum-7]))+1;
    }
    cout<<(dp[X]>=MAX?-1:dp[X])<<endl;
    return 0;
}

发表于 2019-10-10 10:30:00 回复(5)
pein531头像 pein531
背包问题，直接用动态规划即可，对于某一个重量weight，如果weight-3，weight-5，weight-7都凑不出来，那weight也凑不出来。否则状态转移方程为dp[weight] = min(dp[weight - 3], dp[weight - 5], dp[weight - 7]) + 1。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int X = Integer.parseInt(br.readLine().trim());
        int[] dp = new int[10001];     // X的范围是[1,10000]
        Arrays.fill(dp, 10001);
        // 0,1,2,4无法装满
        dp[3] = dp[5] = dp[7] = 1;    // 这三种情况只需要一个货物
        dp[6] = 2;                    // X=6时需要两个重为3的货物
        for(int weight = 8; weight <= X; weight++){
            // weight这个重量减去3,5,7都凑不出来，因此weight也凑不出来
            if(dp[weight - 3] == 10001 && dp[weight - 5] == 10001 && dp[weight - 7] == 10001)
                dp[weight] = 10001;
            else
                dp[weight] = Math.min(dp[weight - 3], Math.min(dp[weight - 5], dp[weight - 7])) + 1;
        }
        System.out.println(dp[X] != 10001? dp[X]: -1);
    }
}


发表于 2021-02-19 16:27:22 回复(0)
炊烟晚霞头像 炊烟晚霞 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = n/7; i >= 0; i--) {
            for (int j = n/5; j >= 0; j--) {
                if (i*7 + j*5 > n) {
                    continue;
                } else if (i*7 + j*5 == n) {
                    System.out.println(i+j);
                    return;
                } else if ((n - i*7 - j*5) % 3 == 0) {
                    int k = (n - i*7 - j*5) / 3;
                    System.out.println(i+j+k);
                    return;
                }
            }
        }
        System.out.println(-1);
    }
}

发表于 2020-08-25 21:14:10 回复(0)
叶挽秋头像 叶挽秋 
import java.util.*;
// X<=14的时候每一种值是特殊的，将结果枚举出来
// X>14的时候可以将它拆为两个部分（7+X%7）+7*（X/7-1）
// 前一部分是<=14的部分，后一部分是7的整数倍
// 例如对于18，可以拆为11+7，11需要3个货物，7需要一个，答案就是4
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int [] r14 = {-1, -1, -1, 1, -1, 1, 2, 1, 2, 3, 2, 3, 2, 3, 2};
        int X = scanner.nextInt();
        if (X <= 14) {
            System.out.println(r14[X]);
        } else {
            int temp = X / 7 - 1;
            System.out.println(temp + r14[X % 7 + 7]);
        }
    }
}
发表于 2020-02-16 12:23:51 回复(0)
卑微java不想去搞测试😭😭😭头像 卑微java不想去搞测试😭😭😭
java代码-动态规划
发表于 2019-09-30 14:52:04 回复(0)
宇智波亦翼头像 宇智波亦翼
最简单粗暴方法，看7的余数，如果是奇数，+1，如果是偶数+2
x=int(input())
def find(x):
    if x==1 or x==2 or x==4 :
         return -1
    count=x//7
    res=x%7
    if res==0:
        return count
    elif res==1 or res==3 or res==5:
        count=count+1
        return count
    elif res==2 or res==6 or res==4:
        count=count+2
        return count
    else:
        return -1
if __name__=='__main__':
    print(find(x))
发表于 2019-08-15 15:03:27 回复(0)
lentolove头像 lentolove 
public class Main {
    /**
     * 哎，一直在分析哪些可以装满哪些不能装满的情况，结果发现只有1，2，4不能装满...rlg
     * 参考了 "皮皮虾没有虾的"同学的分析才明白：
     * 对7取余，余数为1，2，3可以装满，1可以视为1+7=3+5，count+1；
     * 余数为2，4，6可对应9，11，13的情况...... count +=2;
     */
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int x = Integer.parseInt(bf.readLine());
        if (x == 1 || x == 2 || x == 4) {
            System.out.println(-1);
        } else {
            int count = 0;
            count += x / 7;
            x = x % 7;
            if (x == 0) {
                System.out.println(count);
            } else {
                System.out.println(x % 2 == 0 ? count + 2 : count + 1);
            }
        }
    }
}
发表于 2019-08-05 10:54:10 回复(0)
Ankang0320头像 Ankang0320
        回溯法，因为树的规模会很庞大，所以要在dfs中加入提前退出条件，当找到组合方法后，后面的所有枝全部剪掉。每一次dfs的优先关系为先7后5后3，这样第一个找到的组合方法使用的箱子数目最少。因为在找到第一个组合之前，回溯的关系保持，在找到第一个组合之后，也不再需要回溯了。 
#include<iostream>
#include<vector>
using namespace std;
void dfs(vector<int>& temp,int target,int val);//回溯法
vector<vector<int>> res;//保存组合方法
bool flag=true;//是否已找到方法
int main()
{
    int target;
    cin>>target;
    vector<int> temp;//方法暂存变量
    dfs(temp,target,7);//先7
    dfs(temp,target,5);//后5
    dfs(temp,target,3);//后3
    if(res.empty())
        cout<<"-1"<<endl;//没有方法
    else
        cout<<res[0].size()<<endl;//输出货物最少的方法
    return 0;
}
void dfs(vector<int>& temp,int target,int val)
{
    temp.push_back(val);//当前选取的货物放入方法暂存
    if(target==val)//箱子装满
    {
        res.push_back(temp);//当前方法放入结果
        flag=false;//已找到方法
    }
    //不是3选1 而是优先级 7>5>3 否则正确组合可能被跳过
    if(target-val>=7&&flag)//当前剩余值大于等于7 
        dfs(temp,target-val,7);//先放7
    if(target-val>=5&&flag)//当前剩余值大于等于5
        dfs(temp,target-val,5);//再放置5
    if(target-val>=3&&flag)//当前剩余值大于等于3
        dfs(temp,target-val,3);//再放置3
    temp.pop_back();//尾回溯 删除本轮添加的货物
}
        DP解法。dp[i]代表装满重量为i的箱子所需的最少货物数目，那么dp[i]=min(dp[i-3],dp[i-5],dp[i-7])+1。初始化并模拟递推过程即可。使用INT_MAX代表不能被装满。 
#include<iostream>
#include<vector>
#include<limits.h>// for INT_MAX
using namespace std;
int main()
{
    int target;
    cin>>target;
    vector<int> dp(target+1,INT_MAX);//dp[i] 装满体积为i的箱子所需最少货物数目
    dp[3]=1;
    dp[5]=1;
    dp[7]=1;
    dp[6]=2;//初始化
    for(int i=8;i<=target;i++)//递推过程
    {
        int a=dp[i-3],b=dp[i-5],c=dp[i-7];//a b c分别代表i-3 i-5 i-7再装一个货物
        if(a==INT_MAX&&b==INT_MAX&&c==INT_MAX)
            dp[i]=INT_MAX;//表示i不能被被装满
        else
            dp[i]=min(min(a,b),c)+1;//最少的货物数目+1
    }
    if(dp[target]==INT_MAX)
        cout<<"-1"<<endl;//不能被被装满
    else
        cout<<dp[target]<<endl;//输出最少货物数目
    return 0;
}

编辑于 2019-07-16 22:55:10 回复(0)
Polestar_a头像 Polestar_a 
X = int(input())
dp = [float('inf')]*8
dp[3],dp[5],dp[6],dp[7]=1,1,2,1

if (X<8):
    res = dp[X] 
else:
    for i in range(8, X+1):
        temp = min(dp[i-3], dp[i-5], dp[i-7])
        if temp==float('inf'):
            dp.append(float('inf'))
        else:
            dp.append(temp+1)
    res = dp[X]
print(res) if res !=float('inf') else print(-1)

发表于 2019-07-07 15:10:54 回复(0)
无心2019头像 无心2019 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x;
    cin>>x;
    int a[15]={ -1, -1, -1, 1, -1, 1, 2, 1, 2, 3, 2, 3, 2, 3, 2};
    if(x<=14)
        cout<<a[x];
    else
    {
        int res=(x-7)/7;
        res+=a[7+x%7];
        cout<<res;
    }
    return 0;
}

发表于 2019-07-01 19:36:21 回复(0)
tuweilong头像 tuweilong 
/*
回溯法。
从7开始试，找到第一个正好能装满的，便是答案。
*/
import java.util.*;

public class Main {
    static int ans = Integer.MAX_VALUE;
    static boolean flag = false;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        leastGoods357(0, n);
        if (ans == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }

    static void leastGoods357(int cnt, int n) {
        if (flag) return;
        if (n == 0) {
            ans = Math.min(ans, cnt);
            flag = true;
            return;
        } else if (n < 0) {
            return;
        } else {
            leastGoods357(cnt + 1, n - 7);
            leastGoods35(cnt + 1, n - 5);
            leastGoods3(cnt + 1, n - 3);
        }
    }

    static void leastGoods35(int cnt, int n) {
        if (flag) return;
        if (n == 0) {
            ans = Math.min(ans, cnt);
            flag = true;
            return;
        } else if (n < 0) {
            return;
        } else {
            leastGoods35(cnt + 1, n - 5);
            leastGoods3(cnt + 1, n - 3);
        }
    }

    static void leastGoods3(int cnt, int n) {
        if (flag) return;
        if (n == 0) {
            ans = Math.min(ans, cnt);
            flag = true;
            return;
        } else if (n < 0) {
            return;
        } else {
            leastGoods3(cnt + 1, n - 3);
        }
    }
}

发表于 2019-06-28 16:51:58 回复(0)
许愿论文答辩顺利通过顺利毕业🙏头像 许愿论文答辩顺利通过顺利毕业🙏
/*
对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
*/
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;

int main()
{
 //ifstream cin("test.txt");
 int n,i,j;
 while(cin>>n)
 {
   if(n==1||n==2||n==4)  //1 2 4装不满
       cout<<"-1"<<endl;
   else
   {
      int count=0;
      count+=n/7; //对7取余，对余数进行讨论即可
      n=n%7;
      if(n==3||n==5||n==1)  
         count+=1;
      if(n==2||n==4||n==6)  
         count+=2;
      cout<<count<<endl;
   }
 }
 return 0;
}
发表于 2019-07-10 21:30:22 回复(3)
精通Java外卖员头像 精通Java外卖员
好像没什么人跟我同个思路。。分享一下吧。
3,5,7的最小公倍数为105，也就是说只要数字大于105，那么只需要判断它模105剩余的数的问题了。
代码非常精简，对比了一下前面用dp的老哥们速度差不多。考虑边界的问题也不多，可以作为参考。 
import java.util.Scanner;

public class Main {
	static int temp = 0;
	public static void dfs(int count, int rest) {
		if (rest < 0) {//如果-3，-5或者-7小于0了，说明凑不齐，赶紧溜了
			return;
		}
		if (rest == 0) {
			System.out.println(temp*15+count);
			System.exit(0);
		}
		dfs(count + 1, rest - 7);
		dfs(count + 1, rest - 5);
		dfs(count + 1, rest - 3);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		temp = n / 105;
		dfs(0, n % 105);
		System.out.println(-1);
	}
}


发表于 2019-08-08 19:55:10 回复(4)
忧郁的小黑头像 忧郁的小黑
当前题目解答： 
private static int calc(int a) {
        int h1 = 3;
        int h2 = 5;
        int h3 = 7;
        int max7 = a / h3;
        int max5 = 0;
        int max3 = 0;
        int i7 = max7;
        int i5 = 0;
        int i3 = 0;
        for (; i7 >= 0; i7--) {
            max5 = (a - i7 * h3) / h2;
            int a2 = (a - i7 * h3);
            i5 = max5;
            for (; i5 >= 0; i5--) {
                if ((a2 - i5 * h2) % h1 == 0) {
                    max3 = (a2 - i5 * h2) / h1;
                    return (i7 + i5 + max3);
                }
            }
        }
 
        return -1;
    }


升级版题目，货物重量可输入，严格来说货物重量可变化才是最终的解答，因为货物重量组合不同的时候之前的很多解题答案就都不正确了。 
/**
     * 升级版来一个，货物的重量也可输入
     * 参数a：总重量
     * h1: 最轻的货物
     * h2：次轻的货物
     * h3：最重的货物
     */
    private static int calc(int a, int h1, int h2, int h3) {
        // 最重的货物直接装满
        if(a % h3 == 0){
            return a / h3;
        }
        
        // 尝试用最重的两种货物装满
        int result1 = -1;
        int n1 = a / h3;
        while(n1 >= 0){
            int unUse1 = a - n1 * h3;
            if(unUse1 % h2 == 0){
                // 满足条件，退出循环
                result1 = n1 + unUse1 / h2;
                break;
            }
            // 去掉一个最重的货物再尝试
            n1--;
        }

        // 最后尝试三种货物组合
        int result2 = -1;
        n1 = a / h3;
        // 是否结束循环
        boolean flag = false;
        while(n1 >= 0){
            int unUse1 = a - n1 * h3;
            int n2 = unUse1 / h2;
            while(n2 >= 0){
                int unUse2 = unUse1 - n2 * h2;
                if(unUse2 % h1 == 0){
                    result2 = n1 + n2 + unUse2 / h1;
                    flag = true;
                    break;
                }
                n2--;
            }
            if(flag){
                break;
            }
            // 去掉一个最重的货物再尝试
            n1--;
        }

        if(result1 == -1){
            // 当最重的两种货物组合无法装满时，返回三种货物组合结果
            return result2;
        }
        if(result2 == -1){
            // 当三种货物组合无法装满时，返回最重的两种货物组合结果
            return result1;
        }

        if(result1 == -1 && result2 == -1){
            // 所有组合都无法装满
            return -1;
        }
        // 当最终的两种货物组合和三种货物组合都能装满时，返回数量最少的那个组合结果
        return result1 > result2 ? result2 : result1;
    }


发表于 2023-01-12 23:16:09 回复(0)
C++
Y2580头像 Y2580 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x;
    cin >> x;
    for(int i = 0; i <= x / 3; ++i)
        for(int j = 0; j <= (x - 3 * i) / 5; ++j)
            for(int k = 0; k <= (x - 3 * i - 5 * j) / 7; ++k)
            {
                if(x == 3*i + 5*j + 7*k)
                {
                    cout << i + j + k;
                    return 0;
                }
            }
    
    cout << -1;
    return 0;
}
//因为要求最少数量，所以尽量多放重的货物，所以第一层循环代表重量为3，第二层循环代表重量为5的货物，第三层代表
//重量为7，直接三层循环暴力破解
发表于 2022-04-19 08:25:38 回复(0)
C++
Acmen_沉梦昂志头像 Acmen_沉梦昂志 
const int maxn = 10000+5;
#include<iostream>
#include<vector>
#include<cstring>
int dp[maxn];
using namespace std;
int main(){
    int X;
    cin >> X;
    //dp[0] = 0;
    memset(dp,0x3f3f3f,sizeof dp);
    dp[0] = 0;
    vector<int> goods = {3,5,7};
    for(int i = 1;i <= X;i++){
        for(int j = 0;j < 3;j++){
            if(i - goods[j] >= 0){
                if(dp[i-goods[j]]!=1061109567)
                dp[i] = min(dp[i],dp[i-goods[j]] + 1);
            }
        }
    }
    //for(int x : dp) cout << x << " ";
    //cout << endl;
   if(dp[X] == 1061109567) cout << -1 << endl;
   else cout  << dp[X] << endl;
   return 0;
}
经典背包问题
发表于 2022-02-07 21:25:07 回复(0)
Python
王子的诱惑头像 王子的诱惑 
递归
#coding=utf-8
def k5(n):#对于5与3的分配
    d,f,r=n%5,1,n//5#对n取余
    while d%3!=0:#如果余数是3的倍数就可以组合
        d+=5#如果不是就加5
        r-=1
        if d>n:#直到超过n那就说明不能组合
            f=0
            return -1
            break
    if f:
        return d//3+r#d//3是3个数，r是5的个数
            
def k7(n):#对于7与（5&3）的分配
    d,f,re=n%7,1,n//7#对n取余
    while k5(d)==-1:#如果余数是可以用3与5组合，那么就成立
        d+=7#不能组合就加7
        re-=1
        if d>n:#超过时候不能成立
            f=0
            return -1
            break
    if f:
        return k5(d)+re#k5(d)是5与3组合后总数，re是7的个数

while 1:
    try:
        x=int(input())
        print(k7(x))
    except:
        break

发表于 2020-08-17 10:59:34 回复(0)
嫌疑人*X头像 嫌疑人*X
//回溯
#include<bits/stdc++.h>
using namespace std;

void helper(vector<int> &weight,int target,int &res,int cur,int start){
    if(start < 0) return;
    if(target % weight[start] == 0){
        res = min(res,cur + target / weight[start]);
        return;
    }
    for(int i = target / weight[start]; i >= 0; --i){
        if(cur + i >= res) break;
        helper(weight,target - weight[start] * i,res,cur + i,start - 1);
    }
}

int getNum(vector<int> &weight,int target){
    int res = INT_MAX;
    int start = weight.size() - 1;
    int cur = 0;
    helper(weight,target,res,cur,start);
    return (res == INT_MAX)?-1:res;
}



int main(){
    int X;
    cin>>X;
    vector<int> weight;
    weight.push_back(3);
    weight.push_back(5);
    weight.push_back(7);
    
    cout<<getNum(weight,X)<<endl;
    
    return 0;
}
发表于 2020-06-01 18:40:20 回复(0)
提交观点

问题信息

C++工程师 贪心 动态规划 快手 2019 游戏研发工程师 Java工程师
上传者：小小
难度：
42条回答 9672浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最少数量货物装箱问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号