AtCoder Educational DP Contest E - Knapsack 2

題目鏈接:https://atcoder.jp/contests/dp/tasks/dp_e

這題還蠻有趣的

他的重量開到10⁹導致不能用上一題(常規0/1背包)的做法去做

要把價值當做dp轉移,去找當前價值所需的最小重量

最後找到的最大的小於重量限制的價值就是答案

以下為code

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

#define AC ios::sync_with_stdio(0),cin.tie(0);

int main()

{

AC

int n,w,r=0;

cin>>n>>w;

vector<ll> dp(100001,1e10);

dp[0]=0;

for(int i=0;i<n;i++)

{

int wei,val;

cin>>wei>>val;

for(int j=100000;j>=val;j--)

dp[j]=min(dp[j],dp[j-val]+wei);

}

for(int i=1;i<dp.size();i++)

if(dp[i]<=w) r=i;

cout<<r<<'\n';

}