题解 - Vijos

7

#include <iostream>
using namespace std;
int v[30050],w[30050],s[30050],dp[30050];
int main() {
int i,j,n,m;
cin>>m>>n;
for(i=1;i<=n;i++){
cin>>w[i]>>v[i];
}
for(i=1;i<=n;i++){
for(j=m;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]*w[i]);
}
}
cout<<dp[m];
return 0;
}

3

hahayang LV 10 @ 8 年前

01背包。

var
  v, p:array[1..25] of longint;
  f:array[0..30000] of qword;
  n, m, i, j:longint;
begin
  readln(n, m);
  for i:=1 to m do readln(v[i], p[i]);
  fillchar(f, sizeof(f), 0);
  for i:=1 to m do
    for j:=n downto v[i] do if f[j-v[i]]+v[i]*p[i]>f[j] then f[j]:=f[j-v[i]]+v[i]*p[i];
  write(f[n])
end.

2

j18tm01 LV 10 @ 4 年前

背包问题主要是背模板，这里收录了一些模板

一些复杂的背包问题（如泛化物品）未收录

01背包问题：

无优化

for(int i=1;i<=n;i++)
{
    for(int c=0;c<=m;c++)
    {
        f[i][c]=f[i-1][c];
        if(c>=w[i])
        f[i][c]=max(f[i][c],f[i-1][c-w[i]]+v[i]);
    }
}

一维数组优化：

for(int i=1;i<=n;i++)
{
    for(int c=m;c>=0;c--)
    {
        if(c>=w[i])
        f[c]=max(f[c],f[c-w[i]]+v[i]);
    }
}

更进一步的常数优化：

for(int i=1;i<=n;i++)
{
    sumw+=w[i];
    bound=max(m-sumw,w[i]);
    for(int c=m;c>=bound;c--)
    {
        if(c>=w[i])
        f[c]=max(f[c],f[c-w[i]]+v[i]);
    }
}

完全背包问题：

for(int i=1;i<=n;i++)
{
    for(int c=0;c<=m;c++)
    {
        if(c>=w[i])
        f[c]=max(f[c],f[c-w[i]]+v[i]);
    }
}

多重背包问题：

for(int i=1;i<=n;i++)
{
    if(w[i]*a[i]>m)
    {
        for(int c=0;c<=m;c++)
        {
        if(c>=w[i])
        f[c]=max(f[c],f[c-w[i]]+v[i]);
        }
    }
    else
    {
         k=1;amount=a[i];
         while(k<amount)
         {
             for(int c=k*w[i];c>=0;c--)
             {
                 if(c>=w[i])
                 f[c]=max(f[c],f[c-w[i]]+k*v[i]);
             }
             amount-=k;
             k<<=1;
         }  
         for(int c=amount*w[i];c>=0;c--)
         {
             f[c]=max(f[c],f[c-w[i]]+amount*v[i]);
         }
    } 
}

下面来到我们的正题：首先判断是否为背包问题，可见其背包就是money的总数，质量就是重要度*money

可以套用背包问题

有根据其特性可知这是01背包

到此建模完成，思考+读题用时3min

#include<iostream> 
#include<cstdio> 
using namespace std; 
int main(){ 
    int n,m,i,j,v,im,dp[30003]={0}; 
    scanf("%d%d",&n,&m); 
    for(i=1;i<=m;i++){ 
      scanf("%d%d",&v,&im); 
      for(j=n;j>=v;j--){ 
        dp[j]=max(dp[j-v]+v*im,dp[j]); 
      }} 
    printf("%d",dp[n]); 
    return 0;}

求赞

2

学霸wx LV 7 @ 8 年前

良心AC
/*
algorithm:Zero_One_Pack
written by wx
time:2016/10/16 4:05
/
#include <stdio.h>
using namespace std;
int max(int a,int b)
{
if(a>b)return a;
return b;
}
int main()
{
int n,v,cost[30],g[30],i,j,f[30001]={};
scanf("%d%d",&v,&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&cost[i],&g[i]);
g[i]=cost[i];
}
for(i=1;i<=n;i++)
{
for(j=v;j>=cost[i];j--)
f[j]=max(f[j],f[j-cost[i]]+g[i]);
}
printf("%d",f[v]);
return 0;
}

1

aph。 (chenqianrong) LV 10 @ 3 年前

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

int w[30],v[30],f[50000];
int n,m;
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
        w[i]*=v[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            if(j>=v[i])
            {
                f[j]=max(f[j],f[j-v[i]]+w[i]);
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

1

川建国小号 LV 6 @ 4 年前

必过
#include<bits/stdc++.h>
using namespace std;
long long w[10001],v[10001],a[802003],n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=m;i++){
for(int j=n;j>=w[i];j--){
a[j]=max(a[j],a[j-w[i]]+v[i]*w[i]);
}
}
cout<<a[n];
return 0;
}

1

2351599120 LV 9 @ 7 年前

裸的01背包...

#include<bits/stdc++.h>
using namespace std;
int a[26],f[30001],x[26];
int main(){
    int n,m;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&x[i]);
    for(int i=1;i<=n;i++)
        for(int j=m;j>=a[i];j--)
            f[j]=max(f[j],f[j-a[i]]+a[i]*x[i]);
    printf("%d",f[m]);
    return 0;
}

1

4399王水 LV 7 @ 7 年前

//题目中价值和重要度乘起来，就相当于01背包中de价值；
//题目中的价值相当于01背包的重量，然后这就是一个模板题；
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int wr[26][30000];
int im[26];
int zi[26];
int v[26];
int main()
{int mem,n;
cin>>mem>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>im[i];
}
memset(wr,0,sizeof(wr));
for(int i=1;i<=n;i++)
zi[i]=v[i]*im[i];
for(int i=1;i<=n;i++)
{
for(int j=mem;j>=0;j--)
{if(j>=v[i])wr[i][j]=max(wr[i-1][j-v[i]]+zi[i],wr[i-1][j]);
else wr[i][j]=wr[i-1][j];
}
}

cout<<wr[n][mem];

return 0;
}

0

RP++ (贪吃蛇) LV 8 @ 4 年前

#include <bits/stdc++.h>
using namespace std;
int dp[1000011], v[1000010], w[1000011], num[1000011], s = 0, p, k, l, n, m;
int main() {
    cin >> n>>m;
    for (int i = 1; i <= m; i++) cin >> v[i] >> w[i];
    for (int i = 1; i <= m; i++)
        for (int j = n; j >= v[i]; j--) dp[j] = max(dp[j], dp[j - v[i]] + w[i]*v[i]);
    cout << dp[n];
    return 0;
}

0

2132B LV 7 @ 4 年前

dp万岁！！！

#include<bits/stdc++.h>
using namespace std;
int t,n,dp[30020],a[20020],b[20020];
int main()
{
    memset(dp,0,sizeof(dp));
    cin>>t>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i],b[i]*=a[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=t;j>=a[i];j--)
            dp[j]=max(dp[j-a[i]]+b[i],dp[j]);
    }
    cout<<dp[t]<<endl;
    return 0;
}

0

清风breeze LV 8 @ 7 年前

#include<cstdio>
#include<iostream>
int dp[1000001];
int w[1000001], val[1000001];
int main() {
    int t, m;
    scanf("%d%d", &t, &m);
    for(int i=1; i<=m; i++) {
        int x;
        scanf("%d%d", &w[i], &x);
        val[i]=w[i]*x;
    }
    for(int i=1; i<=m; i++)
        for(int j=t-w[i]; j>=0; j--)
            dp[j+w[i]]=std::max(dp[j]+val[i], dp[j+w[i]]);
    printf("%d", dp[t]);
    return 0;
}

0

jw/\s LV 8 @ 7 年前

典型的01背包
#include<bits/stdc++.h>
using namespace std;
int n,m,val,like;
int f[30001];

int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d",&val,&like);
for(int j=n;j>=val;--j){
f[j]=max(f[j],f[j-val]+val*like);
}
}
printf("%d",f[n]);
return 0;
}

0

LYY同学 LV 8 @ 7 年前

#include <iostream>

/* run this program using the console pauser or add your own getch, system("pause") or input loop /
using namespace std;
int s[30][300010]={}; //定义一个存储数组
int main(int argc, char* argv)
{
int m,n,a[30]={0},b[30]={0},i,j;
cin>>m>>n;
for(i=1;i<=n;i++)
{
cin>>a[i]>>b[i]; //循环输入价格数组a[i]和重要成度数组b[i]
}
for(i=1;i<=n;i++)
{
for(j=0;j<=m;j++) //双重循环循环 1~1000（输入实例）
{
if(j>=a[i]) //如果j大于a[i]（商品价格）
s[i][j]=max(s[i-1][j],s[i-1][j-a[i]]+a[i]*b[i]); //比较【下一件商品】和【下一件商品的1~1000-物品价格】（max是指比较两个中最大的那个数，地球人都知道，哈哈）
else
s[i][j]=s[i-1][j]; //否则，把下一件商品赋值给s[i][j];
}
}
cout<<s[n][m-1]; //输出结果
return 0;
}

0

你们的爸爸 LV 9 @ 7 年前

#include<iostream>
using namespace std;
int v[26]={0},p[26]={0};
int f[26][30010]={0};
int main()
{
int m,n;
cin>>m>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>p[i];
}
for(int i=1;i<=n;i++)
for(int V=0;V<=m;V++)
{
if(V>=v[i])
f[i][V]=max(f[i-1][V],f[i-1][V-v[i]]+p[i]*v[i]);
else
f[i][V]=f[i-1][V];
}
cout<<f[n][m-1];
return 0;
}

0

lshstc LV 8 @ 8 年前

#include <iostream>
using namespace std;
int v[30050],w[30050],s[30050],dp[30050];
int main() {
int i,j,n,m;
cin>>m>>n;
for(i=1;i<=n;i++){
cin>>w[i]>>v[i];
}
for(i=1;i<=n;i++){
for(j=m;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]*w[i]);
}
}
cout<<dp[m];
return 0;
}

0

刘天弘 LV 7 @ 8 年前

#include<cstdio>
using namespace std;
long long n,m,v[1000001],p[1000001],f[1000001];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&v[i],&p[i]);
    for(int i=1;i<=m;i++)
    {
        for(int j=n;j>=v[i];j--)
        {
            if(f[j-v[i]]+v[i]*p[i]>f[j])f[j]=f[j-v[i]]+v[i]*p[i];
        }
    }
    printf("%d\n",f[n]);
}

0

刘天弘 LV 7 @ 8 年前

#include<cstdio>
using namespace std;
long long n,m,v[1000001],p[1000001],f[1000001];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d%d",&v[i],&p[i]);
for(int i=1;i<=m;i++)
{
for(int j=n;j>=v[i];j--)
{
if(f[j-v[i]]+v[i]*p[i]>f[j])f[j]=f[j-v[i]]+v[i]*p[i];
}
}
printf("%d\n",f[n]);
}

0

WYN LV 8 @ 8 年前

var 
    n,m,i,j:longint;
    a,b:array[1..1000000] of qword;
    f:array[-30..1000000] of qword;
begin
    readln(n,m);
    for i:=1 to m do readln(a[i],b[i]);
    for i:=1 to m do
        for j:=n downto a[i] do 
            if f[j-a[i]]+a[i]*b[i]>f[j] 
                then f[j]:=f[j-a[i]]+a[i]*b[i];
    writeln(f[n]);
end.

0

jcsyjqj LV 8 @ 8 年前

var m,n,i,j:longint;
k,v:array[1..25] of longint;
f:array[0..1000000] of longint;
begin
readln(m,n);
for i:=1 to n do
readln(k[i],v[i]);
for i:=1 to n do
for j:=m downto k[i] do
if f[j-k[i]]+k[i]*v[i]>f[j] then
f[j]:=f[j-k[i]]+k[i]*v[i];
writeln(f[m]);
end.

0

radia LV 7 @ 8 年前

暴搜略剪枝

#include <iostream>
using namespace std;
int t=0,w[1000],v[1000], c,k;
void bs(int bj, int p,int c)
{
if(c<=0)
return;
if(bj>k){

t=max(t,p);
return;
}
else{
bs(bj+1,p+w[bj],c-v[bj]);
bs(bj+1,p,c);

}
}
int main()
{
cin>>c>>k;
int i;
for(i=1;i<=k;i++){
cin>>v[i]>>w[i];
w[i]=w[i]*v[i];
}
bs(1,0,c);
cout<<t;
return 0;
}

学霸wx @ 8 年前

...你牛

题解

203 条题解

开心的金明

信息

状态

开发

支持

题解

203 条题解

开心的金明

信息

状态

开发

支持

还没有账户？

登录