首页 > 试题广场 >

最少数量货物装箱问题

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

数据范围:

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


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

输入

4

输出

-1

说明

无法装满 
示例2

输入

8

输出

2

说明

使用1个5公斤,1个3公斤货物 
#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)
//动态规划背包问题
#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)
#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)
背包问题,直接用动态规划即可,对于某一个重量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)
最简单粗暴方法,看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)
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)
        回溯法,因为树的规模会很庞大,所以要在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)
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)
#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)
/*
回溯法。
从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)
好像没什么人跟我同个思路。。分享一下吧。
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)
#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)
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)
递归
#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)
//回溯
#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)