试题算法训练装箱问题-创新互联
试题 算法训练 装箱问题
本文标题:试题算法训练装箱问题-创新互联
文章转载:http://scyanting.com/article/gscjd.html
资源限制
在成都网站建设、做网站过程中,需要针对客户的行业特点、产品特性、目标受众和市场情况进行定位分析,以确定网站的风格、色彩、版式、交互等方面的设计方向。创新互联还需要根据客户的需求进行功能模块的开发和设计,包括内容管理、前台展示、用户权限管理、数据统计和安全保护等功能。
内存限制:256.0MB C/C++时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s
问题描述
有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30),每个物品有一个体积(正整数)。
要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
输入格式
第一行为一个整数,表示箱子容量;
第二行为一个整数,表示有n个物品;
接下来n行,每行一个整数表示这n个物品的各自体积。
输出格式
一个整数,表示箱子剩余空间。
样例输入
24 6
8 3 12 7 9 7
样例输出
0
代码–我自己的纯代码–纯模拟–但可以过#include#include
using namespace std;
const int V = 2e4+5;
const int N = 30+5;
int a[N], v, n, book[V], flag[V];
int main()
{int m = 0;
cin >>v >>n;
for (int i = 1; i<= n; i++)cin >>a[i];
sort(a + 1, a + 1 + n);//排序
book[0] = 1;//初始化
for (int i = 1; i<= n; i++)
{if (a[i] >v)break;//如果单个数据就已经大于V了就可以退出了
for (int j = 0; j<= v; j++)
{//第一 是存在的数
//第二 新的数要在范围内
//第三 不能是这次循环里才出现的数
//第四 新出现的数不能是标记过的数
if (book[j] == 1 && j + a[i]<= v && flag[j] == 0 && book[j + a[i]] == 0)
{ book[j + a[i]] = 1;//标记已经出现过
flag[j + a[i]] = 1;//标记这是新出现的数
if (m< j + a[i])m = j + a[i];//取大值
}
}
for (int j = 0; j<= v; j++)flag[j] = 0;//去除标记
if (m == v)break;//如果已经达到V了也可以退出了
}
cout<< v - m;
return 0;
}
大佬代码–动态规划–1维背包#includeusing namespace std;
inline int max(int a, int b) {return a >b ? a : b; }
int v, n;//v为箱子容量 , n个物品
int dp[20003];//箱子容量为i时,可装入的大值
int a[33];
int main()
{cin >>v >>n;
for (int i = 1; i<= n; i++)
cin >>a[i];
for (int i = 1; i<= n; i++)
for (int j = v; j >= a[i]; j--)
dp[j] = max(dp[j - a[i]] + a[i], dp[j]);
cout<< v - dp[v];
return 0;
}
再写写二维背包#includeusing namespace std;
inline int max(int a, int b) {return a >b ? a : b; }
int v, n;//v为箱子容量 , n个物品
int dp[33][20003];
int a[33];
int main()
{cin >>v >>n;
for (int i = 1; i<= n; i++)cin >>a[i];
for (int i = 1; i<= n; i++)
for (int j = 0; j<= v; j++)
{//放的下,取大值
if(j>=a[i])
dp[i][j] = max(dp[i - 1][j - a[i]] + a[i], dp[i - 1][j]);
else
dp[i][j] = dp[i - 1][j];//放不下,直接就等于上一轮
}
cout<< v - dp[n][v];
return 0;
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
本文标题:试题算法训练装箱问题-创新互联
文章转载:http://scyanting.com/article/gscjd.html