DPL_1_F : 0-1 Knapsack Problem II - sinapusu2002 @ ウィキ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_F
ナップザック問題を価値を基準に動的計画法を適用するだけです。
同じ価値なら軽いほうを残す。
それだけ。

#include <iostream>
#include <algorithm>
using namespace std;

int wis[10002]={0};

int main() {
int n,w;
cin>>n>>w;
for(int i=0;i<n;i++){
	int v1,w1;
	cin>>v1>>w1;
	if(w1>w)continue;
	for(int j=10000-v1;j>0;j--){
		if(wis[j]==0)continue;
		int w2=wis[j]+w1;
		if(w2>w)continue;
		int v2=j+v1;
		if(wis[v2]==0){
			wis[v2]=w2;
		}else{
			wis[v2]=min(wis[v2],w2);
		}
	}
	if(wis[v1]==0){
		wis[v1]=w1;
	}else{
		wis[v1]=min(wis[v1],w1);
	}
}
int ans=0;
for(int i=0;i<=10000;i++){
	if(wis[i]>0)ans=i;
}
cout<<ans<<"\n";
}