有重量分别为 3，5，7 公斤的三种货物，和一个载重量为 X 公斤的箱子（不考虑体积等其它因素，只计算重量）
需要向箱子内装满X公斤的货物，要求使用的货物个数尽可能少（三种货物数量无限）
数据范围： 
[编程题]最少数量货物装箱问题
#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)
发表于 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)
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)
/*
回溯法。
从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)
import java.util.*;
// 换零钱
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] coins = {3, 5, 7};
int x = in.nextInt();
int[] dp = new int[x + 1];
Arrays.fill(dp, x + 1);
dp[0] = 0;
for (int coin : coins) {
for (int i = coin; i <= x; i++) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
System.out.print(dp[x] > x ? -1 : dp[x]);
}
}
发表于 2025-04-25 10:09:08
回复(0)
当前题目解答：
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)
问题信息
通过挑战的用户
查看代码-
2023-01-08 01:00:49 -
2022-09-23 18:35:58
-
2022-09-23 12:29:37
-
2022-09-22 23:29:49 -
2022-09-22 16:58:17
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
