装载问题
问题描述
有两艘船,载重量分别是c1、 c2,n个集装箱,重量是wi (i=1…n),且所有集装箱的总重量不超过c1+c2。确定是否有可能将所有集装箱全部装入两艘船。
输入
多个测例,每个测例的输入占两行。第一行一次是c1、c2和n(n<=10);第二行n个整数表示wi (i=1…n)。n等于0标志输入结束。
输出
对于每个测例在单独的一行内输出Yes或No。
样例输入
7 8 2
8 7
7 9 2
8 8
0 0 0
样例输出
Yes
No
解题思路
先计算出 c1
能放下的最大值 max
, 若 c2-max >= 0
,则能装下.
公式
\( f(c,n) = min\{f(c,n-1),f(c-w[n],n-1)\} \)
其中 w 为 weight 集合.
公式计算背包容量剩余c,且剩余n个物品时, 最优解剩余的背包容量.
递归终点
物品数为0,或者背包装不下
我的代码
#include<iostream>
#define NaN 114514
using namespace std;
int min(int,int);
int f(int,int,int[]);
int main(){
while(1){
// sum 物品重量总和, weight 记录装入c1的最大值.
int c1,c2,n,sum = 0,weight;
cin >> c1 >> c2 >> n;
if( n == 0 ){
break;
}
int w[n];
for(int i = 0; i < n; i++){
cin >> w[i];
sum += w[i]; // 计算中重量
}
weight = c1 - f(c1,n,w); // 装入c1的总重量
if( sum - weight <= c2 ){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}
return 0;
}
int min(int a,int b){
return a<b?a:b;
}
int f(int c,int n,int w[]){
if( c < 0 ){ // 如果装不下
return NaN; // 返回无穷大
}
if( n == 0 ){ // 如果没有物品了
return c; // 直接返回背包剩余容量
}
int i = n-1; //下标
return min(f(c,n-1,w),f(c-w[i],n-1,w));
}
标签:西农,OJ,weight,int,sum,P1005,测例,c2,c1
From: https://www.cnblogs.com/orzmiku/p/17644159.html