题解 - Vijos

0

★彭文立★ LV 3 @ 18 年前

看完题马上开写.3分钟,18行.

for i:=1 to n do

for j:=v downto a[i] do

f[j]:=f[j] or f[j-a[i]];

0

老是被封号。。 LV 3 @ 18 年前

用贪心咯，到处都找得到的题。。。

0

GolfGTI LV 4 @ 18 年前

与01背包类似的DP

0

liuhunter LV 3 @ 18 年前

下面说的是O(vn)的算法，有没有O(N^2)的？

0

YJ狗狗 LV 6 @ 19 年前

一个简单的动态规划问题-01背包

f[i][j]=max{f[j],f[j-g[i]+g[i](j-g[i]>=0)}

f[0][j]=0

逐行递推答案即为(V-f[n][v])

-1

Dragon___Killer LV 8 @ 7 年前

#include<bits/stdc++.h> 
using namespace std;
bool f[20030]={1};
int n,u;
int main()
{
    cin >> u >> n;
    for (int i=1;i<=n;i++)
    {
        int k;
        cin >> k;
        for (int j=u;j>=k;j--)
            f[j]=f[j-k]||f[j];
    }
    int MIN = u;
    for (int i=1;i<=u;i++)
        if (f[i]) MIN = i;
    cout<<u-MIN;
}

-1

痞子熊 LV 7 @ 7 年前

#include <iostream>
using namespace std;

int main()
{
int m,n;//m为质量，n为数量
cin>>m>>n;
int* w=new int [n];
for(int a=0;a<n;a++)
{
cin>>w[a];//每个石头的重量
}
int** c=new int* [n+1];
for(int a=0;a<=n;a++)
{
c[a]=new int [m+1];
for(int b=0;b<=m;b++)
{
c[a][b]=0;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(w[i-1]<=j)
{
if(c[i-1][j]<c[i-1][j-w[i-1]]+w[i-1])
{
c[i][j]=c[i-1][j-w[i-1]]+w[i-1];
}
else
{
c[i][j]=c[i-1][j];
}
}
else
{
c[i][j]=c[i-1][j];
}
}
}
cout<<m-c[n][m];
return 0;
}

-1

田一菲 LV 7 @ 7 年前

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
int v[35],V,n,f[20010],ans;
int main()
{
scanf("%d%d",&V,&n);
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
for(int i=1;i<=n;i++)
for(int j=V;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+v[i]);
ans=V-f[V];
printf("%d",ans);
return 0;

}

-1

JimmyChen LV 8 @ 7 年前

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

bool dp[20005];
int v[35];
int n;
int box;

int main() {
    cin >> box >> n;
    memset(v, -1, sizeof v);
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }

    dp[0] = true;
    for (int j = 1; j <= n; j++) {
        for (int i = box; i >= 0; i--) {
            if (i - v[j] >= 0) dp[i] = (dp[i] | dp[i - v[j]]);
        }
    }
    for (int i = box; i >= 0; i--) {
        if (dp[i] != 0) {
            cout << box - i << endl;
            return 0;
        }
    }
    return 0;
}

-1

Saika LV 8 @ 8 年前

N<30 暴力能过么

-1

feidaoluoye LV 9 @ 8 年前

AC留念
#include <iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[20010],w[33];
int d(int x,int m){
int tot =0;
while(x>0)
{
if(x%10==m)
tot++;
x/=10;
}
return tot;
}
int main()
{
int v,n,i,j;
cin>>v>>n;
for(i=0;i<n;++i)
cin>>w[i];
for(i=0;i<n;++i)
for(j=v;j>=w[i];--j)
{
f[j] = max(f[j],f[j-w[i]]+w[i]);
}
cout<<v-f[v];
return 0;
}

你们的爸爸 @ 7 年前

垃圾代码

-1

937337156 LV 8 @ 8 年前

C++代码+题解
http://www.cnblogs.com/937337156Zhang/p/6044475.html

-1

HBat LV 8 @ 8 年前

#include <iostream>
#include <vector>

using namespace std;

vector <int> f,w;

int main()
{
int m,n;
int i,j;
cin>>m>>n;
f.resize(m+1);
w.resize(n+1);
for(i=1;i<=n;++i)
cin>>w[i];
for(i=0;i<=m;++i)
f[i]=0;
for(i=0;i<=n;++i)
for(j=m;j>=w[i];--j)
f[j]=max(f[j],f[j-w[i]]+w[i]);
cout<<m-f[m];
return 0;
}

-1

lrj124 LV 10 @ 8 年前

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 556 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 556 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 556 KiB, score = 10
Accepted, time = 15 ms, mem = 560 KiB, score = 50
代码
#include <algorithm>
#include <iostream>
using namespace std;
int Min = 9999999,v[31],m,n;
inline void dfs(int now,int num) {
  Min = min(Min,now);
  if (num == n+1) return;
  if (now-v[num] >= 0) dfs(now-v[num],num+1);
  dfs(now,num+1);
}
int main (){
  ios :: sync_with_stdio(false);
  cin >> m >> n;
  for (int i = 1;i <= n;i++) cin >> v[i];
  dfs(m,1);
  cout << Min;
  return 0;
}

-1

ljt12138 LV 10 @ 8 年前

弱。。
```c++
#include <bits/stdc++.h>
using namespace std;

bitset<20005> bit;
int main()
{
int n, m, a;
cin >> m >> n;
bit = 0;
bit[0] = 1;
for (int i = 1; i <= n; i++){
cin >> a;
bit |= bit<<a;
}
for (int i = m; i >= 0; i--)
if (bit[i]) {
cout << m-i << endl;
break;
}
return 0;
}
```

-1

fallenangel LV 4 @ 8 年前

var     maxv,n,i,j:longint;
        v:array[0..30] of longint;
        f:array[0..20000] of longint;

function max(x,y:longint):longint;
  begin
        if x>y then max:=x else max:=y;
  end;

begin
        readln(maxv);readln(n);
        for i:=1 to n do readln(v[i]);

        fillchar(f,sizeof(f),0);
        for i:=1 to n do
          for j:=maxv downto v[i] do
                if f[j-v[i]]+v[i]<=maxv then f[j]:=max(f[j-v[i]]+v[i],f[j]);

        writeln(maxv-f[maxv]);
end.

-1

fallenangel LV 4 @ 8 年前

#include<bits/stdc++.h>
using namespace std;

int max(int a,int b){return a>b?a:b;}//求a、b中的较大值 

int main(){
    int maxv,n,f[20001],v[30];//f[i]表示背包重量为i的最优解 
    
    scanf("%d",&maxv);scanf("%d",&n);//读入背包的容量maxv和物品的个数n 
    for (int i=1;i<=n;i++) scanf("%d",&v[i]);//读入每个物品的重量 
    
    memset(f,0,sizeof(f));//f数组初始化 
    for (int i=1;i<=n;i++)
        for (int j=maxv;j>=v[i];j--)
            f[j]=f[j-v[i]]+v[i]>maxv?f[j]:max(f[j-v[i]]+v[i],f[j]);//放得下就取原来的重量与放进之后的较优解否则直接就是原来的解 
            
    printf("%d\n",maxv-f[maxv]);//输出 
}

-1

Moshang LV 6 @ 8 年前

#include

-1

lksjg LV 8 @ 8 年前

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int d[30000+3];
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<=n;i++) d[i]=i;
int v,w;

for(int i=1;i<=m;i++){
scanf("%d",&v);
for(int j=n;j>=0;j--)
if(j>=v&&d[j-v]>=0)

d[j]=min(d[j],d[j-v]);
}
cout<<d[n];
return 0;
}

题解

239 条题解

装箱问题

信息

状态

开发

支持

题解

239 条题解

装箱问题

信息

状态

开发

支持

还没有账户？

登录