#include <stdio.h>
#include <stdlib.h>
int c1, c2, n, w[10]int weight = 0, max = 0
int count1 = 0, count2 = 0//添加的代码
int sum = 0
int arrC1[10], arrC2[10]//用来装C1 C2货船上的货物的重量
void search(int m)
{
if (m == n)
{
if (weight <= c1)
if (weight >= max)
max = weight
}
else
{
weight += w[m]
search(m + 1)
//添加的代码 如果max已被赋值，则c1货船装到了最大重量的货物 函数立即return不再继续执行,
//把返回路径上添加的重量放到c1的数组里
if (max>0 &&c1>=weight &&sum-weight<=c2 )
{
arrC1[count1] = w[m]count1++return
}
weight -= w[m]
search(m + 1)
//添加的代码 如果max已被赋值，则c1货船装到了最大重量的货物 函数立即return不再继续执行,
//把剔除的货物放到c2的数组里
if (max >0 /*&&c1 >= weight*/ &&sum - weight <= c2)
{
arrC2[count2] = w[m]count2++return
}
}
}
int main()
{
int i
scanf("%d%d%d", &c1, &c2, &n)
while (n != 0)
{
for (i = 0i <ni++)
{
scanf("%d", &w[i])sum += w[i]
}
search(0)
if (sum - max <= c2)
{
printf("Yes\n")
//添加的代码 输出c1货船上的货物
printf("c1: ")
for (int i = 0i <count1i++)
printf(" %d ", arrC1[i])
//输出c2货船上的货物
printf("\tc2: ")
for (int i = 0i <count2i++)
printf(" %d ", arrC2[i])
printf("\n")
}
else
printf("No\n")
max = 0
sum = 0
//添加的代码
count1 = 0
count2 = 0
//刚才忘了把weight清0 所以出错了
weight = 0
scanf("%d%d%d", &c1, &c2, &n)
}
return 0
}
想法:是先让c1船尽量装货物是可以的，但是算法应该不对，可以用下面的算法// 前k个数中去任意个数，且这些数之和为s的取法是否存在
int main()
{
int n, i, k1, k2, s, u
cin >>n
for (i=1i<=2*ni++)
cin >>A[i]
int sum = 0
for (i=1i<=2*ni++)
sum += A[i]
memset(dp,0,sizeof(dp))
dp[0][0]=true
// 外阶段k1表示第k1个数，内阶段k2表示选取数的个数
for (k1=1k1<=2*nk1++)// 外阶段k1
{
for (k2=k1k2>=1k2--) // 内阶段k2
for (s=1s<=sum/2s++) // 状态s
{
//dp[k1][s] = dp[k1-1][s]
// 有两个决策包含或不包含元素k1
if (s>=A[k1] &&dp[k2-1][s-A[k1]])
dp[k2][s] = true
}
}
// 之前的dp[k][s]表示从前k个数中取任意k个数，经过下面的步骤后
// 即表示从前k个数中取任意个数
for (k1=2k1<=2*nk1++)
for (s=1s<=sum/2s++)
if (dp[k1-1][s]) dp[k1][s]=true
// 确定最接近的给定值sum/2的和
for (s=sum/2s>=1 &&!dp[2*n][s]s--)
}
