题解 - Vijos

7

/*
作者:larryzhong
题目:p1102 采药
*/

#include <iostream>
using namespace std;

const int maxn = 1010, maxv = 5010;
long long c[maxn], w[maxn], f[maxn][maxv];

int main() {
    int V, n;
    cin >> V >> n;
    for (int i = 1; i <= n; i++)
        cin >> c[i] >> w[i];
    for (int i = 1; i <= n; i++)
        for (int v = 0; v <= V; v++) {
            if (v >= c[i])
                f[i][v] = max(f[i - 1][v], f[i - 1][v - c[i]] + w[i]);
            else
                f[i][v] = f[i - 1][v];
        }
    cout << f[n][V] << endl;
    return 0;
}

2

太子辉 (tiantian2010) LV 5 @ 7 个月前

#include<iostream>
using namespace std;

int t,m;
int w[105],v[105];
int dp[105][1005];//105为物品，1005为最大价值

signed main(){
    cin>>t>>m;
    for(int i=1;i<=m;i++){
        cin>>w[i]>>v[i];
    }
    //递推起点为0，所以不用单独处理
    for(int i=1;i<=m;i++){//逐个决策物品
        for(int j=0;j<=t;j++){//逐个决策背包容量
            if(j>=w[i]){
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
            }else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    //答案在m个物品都看完，且考虑了最大容量的格子
    cout<<dp[m][t];
    return 0;
}

2

lajioj LV 7 @ 7 年前

#include<iostream>
#include<cstdio>
using namespace std;
int w[1005];
int k[1005];
int f[1005]; //一维优化
int main()
{
int n,s;
scanf("%d",&s);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&w[i],&k[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=s;j>=w[i];j--)
{
f[j]=max(f[j-w[i]]+k[i],f[j]);
}
}
printf("%d",f[s]);
return 0;
}

2

琀予 LV 8 @ 7 年前

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
long long t[110],m[110],f[1010][1010];
int main()
{
int a,n;//a表示总时间，n表示山洞里草药的数目
cin>>a>>n;
for(int i=1;i<=n;i++)
cin>>t[i]>>m[i];//循环输入每种草药采摘所需的时间和价值
for(int i=1;i<=n;i++)
for(int j=0;j<=a;j++)
{
if(j>=t[i])//如果总时间大于采药所需时间
f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+m[i]);
else f[i][j]=f[i-1][j];
//对比不采当前草药能获得的最大价值和采当前草药能获得的最大价值
}
cout<<f[n][a]<<endl;//输出最大价值
return 0;
}

2

琀予 LV 8 @ 7 年前

c++ 啦啦啦啦啦啦

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
long long t[110],m[110],f[1010][1010];
int main()
{
int a,n;//a表示总时间，n表示山洞里草药的数目
cin>>a>>n;
for(int i=1;i<=n;i++)
cin>>t[i]>>m[i];//循环输入每种草药采摘所需的时间和价值
for(int i=1;i<=n;i++)
for(int j=0;j<=a;j++)
{
if(j>=t[i])//如果总时间大于采药所需时间
f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+m[i]);
else f[i][j]=f[i-1][j];
}
cout<<f[n][a]<<endl;
return 0;
}

2

琀予 LV 8 @ 7 年前

啦啦啦啦啦啦

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
long long c[1010],w[1010],f[1010][1010];
int main()
{
int V,n;
cin>>V>>n;
for(int i=1;i<=n;i++)
cin>>c[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=V;j++)
{
if(j>=c[i])
f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);
else f[i][j]=f[i-1][j];
}
cout<<f[n][V]<<endl;
return 0;
}

1

PandaCode LV 6 @ 10 个月前

这道题目主要靠01背包
可以使用最经典的核心代码：

for (int i = 1; i <= m; i++)
        for (int j = t; j >= a[i]; j--) f[j] = max(f[j], f[j-a[i]] + b[i]);

代码如下：

/*
作者：PandaCode
题目：P1104 采药
*/
#include<iostream>
using namespace std;
int t, m;
const int N = 1e4 + 5;
const int M = 1e7 + 5;
int a[N], b[N];
int f[M];
int main()
{
    cin >> t >> m;
    for (int i = 1; i <= m; i++)
        cin >> a[i] >> b[i];
    for (int i = 1; i <= m; i++)
    {
        for (int j = t; j >= a[i]; j--)
            f[j] = max(f[j], f[j - a[i]] + b[i]);   
    }   
    cout << f[t] << endl;
    return 0;
}

1

士郎のsaber (hhh_saber) LV 6 @ 3 年前

#include<bits/stdc++.h>
using namespace std;
long long ti[10000],vi[10000],f[10000][10000];
int main()
{
    int v,n;
    cin>>v>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>ti[i]>>vi[i];  
    }
    for(int i=1; i<=n; i++)
        for(int j=0; j<=v; j++)
        {   
          f[i][j]=f[i-1][j];
            if(j>=ti[i])
                f[i][j]=max(f[i][j],f[i-1][j-ti[i]]+vi[i]);
           
        }
    cout<<f[n][v]<<endl;
    return 0;
}

1

红烧清蒸某邓吖 LV 8 @ 4 年前

本题是0/1背包
我关于0/1背包的讲解：【精讲】DP经典问题——0/1背包问题

#include<cstdio>
using namespace std;
int n,t,w,v,f[1001];
int max(int x,int y){
    if(x>y)return x;
    else return y;
}
int main(){
    scanf("%d%d",&n,&t);
    for(int i=1;i<=t;i++)
    {
        scanf("%d%d",&w,&v);
        for(int j=n;j>=w;j--)
            f[j]=max(f[j],f[j-w]+v);        
    }

    printf("%d",f[n]);
}

1

严诚治 LV 6 @ 4 年前

简单的01背包问题

#include<bits/stdc++.h>
using namespace std;
int n,m;
int v[105],w[105];
int dp[1005]; 
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    for(int j=m;j>=v[i];j--)
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    cout<<dp[m];
    return 0;
}

1

江山妹妹 LV 4 @ 4 年前

介是一道标准的01背包辣~
01背包是O(NW)的复杂度
所以是双循环枚举呀
第一层1~n枚举物品
第二层W~w[i]枚举背包容量
tips:w[i]指的是第i个物品的体积呀
第二步要推柿子
没对于每个空间，最大价值有两种决策
放：f[j]
不放:f[j-w[i]]+c[i]
求个最大就好啦
上代码啦：
#include<bits/stdc++.h>
using namespace std;
int W,n;
int w[110],c[110],f[1100];
int main()
{
cin>>W>>n;
for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&c[i]);
for(int i=1;i<=n;i++)
for(int j=W;j>=w[i];j--)f[j]=max(f[j],f[j-w[i]]+c[i]);
cout<<f[W];
}
好简单呢~

1

bfw (bfw) LV 8 @ 5 年前

$01$ 背包模板。 我第一次发题解，大家多多照顾 。

很显然本题的数据范围是 $n \leq 30$ ，完全可以用 $dfs+$ 一些剪枝写过去。

但是，如果 $n,V \leq 1000$ ，那么就只能 $dp$ .

用 $dp[i][j]$ 表示用 $j$ 的容量选择前 $i$ 个物品可以获得的最大价值。

那么，我们需要考虑第 $i$ 个物品。

dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);

前者：不选当前的。

后者：选当前的，背包容量缩小，加上当前的价值。

然而数组下标显然非负，所以要保证 $j \geq v_i$ ，否则就只能选择dp[i-1][j]

二维数组的好处是：**不用考虑循环的正反问题。**

显然可以弄成一维（滚动数组），但是没必要，那样还要研究循环的正反，太麻烦。（当然除非真的有内存的压缩需求）

献上本巨佬的代码。

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

int V,n;
int dp[1001][1001];
int v[1001],w[1001];

inline int read(){char ch=getchar();while(ch<'0' || ch>'9') ch=getchar();
    int x=0;while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x;}

int main(){
    V=read(),n=read();
    for(int i=1;i<=n;i++) v[i]=read(),w[i]=read();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=V;j++){
        dp[i][j]=dp[i-1][j];
        if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
    }
    printf("%d\n",dp[n][V]);
    return 0;
}

1

@魑魅灬魍魉@ LV 5 @ 5 年前

f是动态规划数组。
x为时间，y为价值。
二维时由上一层推来，状态转移方程：
f[i,j]:=max(f[i,j],f[i-1,j-x]+y);
而现在改成了一维，状态要倒着放，
否则当前一层前面的状态会影响目前的操作。
状态转移方程：
f[i]:=f[i-x]+y;
这绝对是最简单的动规写法......
Pascal程序：
var n,m,i,j,x,y,max:longint;
f:array[0..1001] of longint;
begin
readln(m,n);
for i:=1 to n do
begin
readln(x,y);
for j:=m downto x do
if f[j-x]+y>f[j] then
f[j]:=f[j-x]+y;
end;
for i:=1 to m do
if f[i]>max then
max:=f[i];
writeln(max);
end.

1

Quiet_Space_time LV 8 @ 6 年前

现在这么流行DP吗？
我特别喜欢写DFS，不过是个编程的人都知道暴力是不可以过的。
所以我加了最优性剪枝（启发式搜索）
详见代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 105 ;
int n,m,ans;
struct Node{
    int a,b;//a代表时间，b代表价值 
    double f;//性价比 
}node[N];
bool cmp(Node p,Node q) {
    return p.f>q.f;//按性价比排序 
}
int f(int t,int v){//估值函数 
    int tot=0;
    for(int i=1;t+i<=n;i++)
        if(v>=node[t+i].a){
            v-=node[t+i].a;
            tot+=node[t+i].b;
        }
        else 
            return (int)(tot+v*node[t+i].f);
    return tot;
}
void dfs(int t,int p,int v){
    ans=max(ans,v);
    if(t>n) return ;
    if(f(t,p)+v>ans) dfs(t+1,p,v);//判断，如果后面的药品达不到ans就不搜索了 
    if(node[t].a<=p) dfs(t+1,p-node[t].a,v+node[t].b);
}
int main(){
    scanf("%d %d",&m,&n);//读入大小和 
    for(int i=1;i<=n;i++){
        scanf("%d %d",&node[i].a,&node[i].b);
        node[i].f=1.0*node[i].b/node[i].a;//计算性价比
    }
    sort(node+1,node+n+1,cmp);//按性价比排序 
    dfs(1,m,0);
    printf("%d\n",ans);
    return 0;
}

1

3159968027 LV 9 @ 6 年前

//来一份记忆化搜索
#include <cstdio>
#include <cstring>
#include <algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define N 1005
using namespace std;

int n,m,f[N][N],val[N],w[N];
int dfs(int i,int v){
    if (f[i][v]!=-1) return f[i][v];
    if (i==0 || v<=0) return 0;
    if (w[i]>v) f[i][v]=dfs(i-1,v);
    else f[i][v]=max(dfs(i-1,v),dfs(i-1,v-w[i])+val[i]);
    return f[i][v];
}
int main(){
    memset(f,-1,sizeof(f));
    scanf("%d%d",&m,&n);
    For(i,1,n){
        scanf("%d%d",&w[i],&val[i]);
    }
    printf("%d\n",dfs(n,m));
    return 0;
}

1

Elucidator LV 7 @ 6 年前

#include<iostream>
using namespace std;
typedef long long ll;
const int maxx=6666;
int main()
{
ll f[maxx],w[maxx],v[maxx],n,t;
cin>>t>>n;
for(int i=1;i<=n;i++)
cin>>w[i]>>v[i];
for(int i=1;i<=n;i++)
for(int j=t;j>=w[i];j--)
{
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
cout<<f[t];
return 0;
}

1

785822068 LV 7 @ 6 年前

水题，pascal代码见下

program noname01;
var t,m:integer;
  c:array[1..100] of integer;
  w:array[1..100] of integer;
  f:array[1..1000] of integer;
  i,ans:integer;
 procedure zo(cost:integer;weight:integer);
 var v:integer;
 begin
   for v:=t downto cost do
   if f[v-cost]+weight>f[v] then f[v]:=f[v-cost]+weight;
 end;
 begin
 for i:=1 to 1000 do f[i]:=0;
 ans:=0;
  read(t,m);
 for i:=1 to m do
   read(c[i],w[i]);
 for i:= 1 to m do
   zo(c[i],w[i]);
 for i:=1 to t do
   if f[i]>ans then ans:=f[i];
 write(ans);
 end.

1

Bill R. Wilson LV 7 @ 7 年前

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int dp[1000][1000],t[1000],v[1000];
int main(){
    int time_max,item_max,item,time=0;
    memset(dp,0,sizeof(dp));
    memset(t,0,sizeof(t));
    memset(v,0,sizeof(v)); 
    cin>>time_max>>item_max;
    for(item=1;item<=item_max;item++)
        cin>>t[item]>>v[item];
    for(item=1;item<=item_max;item++){
        for(time=time_max;time>=t[item];time--)
            dp[item][time]=max(dp[item-1][time-t[item]]+v[item],dp[item-1][time]);
        for(time=t[item]-1;time>=0;time--)
            dp[item][time]=dp[item-1][time];
    }
    cout<<dp[item_max][time_max]<<endl;
}

1

2585479524 LV 7 @ 7 年前

典型的01背包问题，用一维数组解决，不需要存数据

import java.util.Scanner;

public class Main {
static Scanner in = new Scanner(System.in);
static int n, m;
static int[] dp = new int[105];
public static void main(String[] args) {
n = in.nextInt();
m = in.nextInt();
for (int i = 1; i <= m; i++) {
int a = in.nextInt();
int b= in.nextInt();
for (int j = n; j >= 0; j--) {
if (j >= a) {
dp[j] = Math.max(dp[j], dp[j - a] + b);
}
}
}
System.out.println(dp[n]);
}

}

1

清风breeze LV 8 @ 7 年前

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

题解

303 条题解

采药

信息

状态

开发

支持

题解

303 条题解

采药

信息

状态

开发

支持

还没有账户？

登录