1D dp solution
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, w; cin>>n>>w;
int wt[n+1], value[n+1];
int total_value=0;
for(int i=0;i<n;i++){
cin>>wt[i]>>value[i];
total_value+=value[i];
}
int dp[total_value+1];
dp[0]=0;
for(int i=1;i<=total_value;i++)
dp[i]=1e9+9;
int ans=0;
for(int i=1;i<=n;i++){
for(int j=total_value;j>=value[i-1];j--){
dp[j] = min(dp[j], dp[j-value[i-1]] + wt[i-1]);
if(dp[j]<=w)
ans=max(ans, j);
}
}
cout << ans << endl;
}
It’s not neccessary and harder to intuitively visualise. The reason we have to go from total value to 0 is we are using the previous dp[i][j-object[i].value] . I don’t want this value to have already used object[i] because then I will be double counting.
can you explain it with example ??
why we are not starting total value from zero ?? why reverse loop
In my dp[i][j] ,I stored the minimum weight required to calculate j value using i items
n,w = map(int , input().split())
values = []
weights = []
ans= 0
totalvalues = 0
for i in range(n):
a,b = map(int ,input().split())
weights.append(a)
values.append(b)
totalvalues += b
dp = [ [0 for i in range(totalvalues+1)] for j in range(n+1) ]
for i in range(totalvalues+1):
dp[0][i] = float(“inf”)
for i in range(n+1):
dp[i][0] = 0
for i in range(1,n+1):
for j in range(1,totalvalues+1):
if values[i-1] <= j :
dp[i][j] = min(dp[i-1][j], dp[i-1][j-values[i-1]] + weights[i-1])
else :
dp[i][j] = dp[i-1][j]
for i in range(1,n+1):
for j in range(1,totalvalues + 1):
if dp[i][j] <= w:
ans = j
print(ans)