0
已解决
新手守护
#include<iostream>
#include<cstdio>
using namespace std;
int n,c,wi[110],used[110],ans,flag;
void dfs(int step,int w)
{
if(w>c||flag)
return ;
if(w == c)
{
flag = 1;
ans = c;
return ;
}
for(int i = step;i <= n;i++)
{
if(!used[i])
{
used[i] = 1;
w += wi[i];
dfs(step+1,w);
w -= wi[i];
used[i] = 0;
if(w > ans)
ans=w;
}
}
}
int main()
{
cin>>n>>c;
for(int i = 1;i <= n;i++)
cin>>wi[i];
dfs(1,0);
cout<<ans;
return 0;
}http://judge.codingtang.com/problem/1049/第三个测试点超时，不知原因
2
已采纳
高级光能
这道题是DP中的装箱问题，本蒟蒻只会用DP写
解题思路：
动态规划的核心思想就是将问题划分为n个存在共同子问题的子问题，并将这些子问题的结果计算并存储起来，一般为数组。
本题使用一维数组dp来记录在当前空间下的最大填充体积，dp[j] ->在体积为j的情况下最大填充为dp[j]；由于在对一个物体来说，它有两种状态，放入箱子dp[i-num[j]]+num[j],或者不放入dp[j],我们需要的是这两者中的较大的一个，即：dp[j] = max(dp[j],dp[i-num[j]]+num[j]);
for(int i = 0; i < m;i++)//将给出的物体放入箱子，防止重复计算
{
for(int j = n; j >= num[i]; j--)//判断物体是否放入箱子
{
dp[j] = max(dp[j],dp[j-num[i]]+num[i]);
}
}看懂了吗？望采纳！！
0
中级光能
正如他们所说的
0
资深守护
s
0
资深守护
加速头文件
0
新手天翼
正如他们所说的
0
高级守护
int main()
{
cin>>n>>c;
for(int i=1;i<=n;i++)
cin>>a[i];
f[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=c;j>=a[i];j--)
{
if(f[j]==1||f[j-a[i]]==1)
f[j]=1;
}
}
for(int i=c;i>=0;i--)
if(f[i]==1)
{
cout<<i;
return 0;
}
return 0;
}
0
高级守护
循环控制有问题
0
初级天翼
正如他们所说
0
高级光能
DP
0
高级天翼
DP啊
