只过了第一个和最后一个样例 为什么?

回复帖子 返回题目

@ shuaijason 2017-07-17 22:43
#include <bits/stdc++.h>
using namespace std;
const int maxn=30007;
int n,m,dp[maxn];
struct object{
    int v;
    int sig;
};
    object a[27];
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> a[i].v >> a[i].sig ; 
        dp[i]=a[i].v * a[i].sig ;
    } 
    for(int i=1;i<=m;i++)
        for(int j=n;j>=a[i].v ;j--)
            dp[j]=max(dp[j],dp[j-a[i].v]+dp[i]); 
    cout << dp[n];    
}
@ tangzhide 2017-07-19 20:00 回复

(简单的01背包)你可以这样写:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int w[200],c[200];
int n,V;
int f[50000];
int main()
{
    scanf("%d%d",&V,&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]);
    for(int i=1;i<=n;i++) c[i]=w[i]*c[i];
    for(int i=1;i<=n;i++)
     for(int j=V;j>=w[i];j--)
      f[j]=max(f[j],f[j-w[i]]+c[i]);
    printf("%d",f[V]);
}